[프로그래머스 2018 KAKAO BLIND RECRUITMENT 3차] 방금 그곡 (문자열, ) [C++]

https://programmers.co.kr/learn/courses/30/lessons/17683

코딩테스트 연습 - [3차] 방금그곡

---

신경 쓸게 많은 까다로운 문제였다.

내가 문제를 푼 순서는

1. 입력값으로 주어진 musicInfos를 파싱 했다. - split 함수를 통해 vector <string>으로 바꿨다.

2. 파싱 한 값들 중 HH:MM 형식의 시간 데이터를 int형으로 변환했다. - convert함수를 통해 int형으로 변경

3. string형태의 melody를 split 해줬다. 이유는 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 이므로 #을 처리하기 위해서 각각 분리했다. - melodySplit함수를 통해 vector <string>으로 변경

4. 그리고 원하는 멜로디 라인이 해당 음악에 있는지 체크했다 - check함수를 통해 true/false 리턴

4-1. 나의 풀이는 음 하나하나가 string으로 vector에 들어가 있으므로 체크를 N^2으로 했다.

음이 최대 1439개이므로 N^2해도 백만이라서 괜찮다고 생각했다.

5. 그렇게 TRUE가 반환이 되면, 정답에 대한 정보를 저장했다.

5-1. 왜냐하면 노래의 결과가 두 개 이상이면

• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.

의 조건을 만족해야 하기 때문이다.

---

- 주의해야 할 점은 음악이 여러 개일 경우 처리해주는 것과 "#"을 처리해주는 문제이다.

처음에 먼저 입력된 음악을 체크하지 않아서 테스트 케이스를 통과하지 못했고

ABC#인 경우 ABC를 찾는데 true를 반환해서 통과하지 못했다.

C#을 한 문자열로 봤다면 C때 일치하지 못해서 false가 반환이 됐을 것이다.

#include <string>
#include <vector>
#include <iostream>
#include <sstream>

using namespace std;

vector<string> melodySplit(string melody){
    vector<string> result;
    string temp;
    temp += melody[0];
    for(int i = 1 ; i < melody.size() ; i++){
        if(melody[i] >= 'A' && melody[i] <= 'Z'){
            result.push_back(temp);
            temp.clear();
        }
        temp += melody[i];
    }
    result.push_back(temp);
    return result;
}

bool check(int startTime, int endTime, string name, string melody, string target) {
    int timeRange = endTime - startTime;
    vector<string> melodys = melodySplit(melody);
    vector<string> fullMelody;
    vector<string> targetVector = melodySplit(target);
    
    // 시간만큼 fullMelody를 생성
    for(int i = 0 ; i < timeRange ; i++){
        fullMelody.push_back(melodys[i % melodys.size()]);
    }
    
    for(int i = 0 ; i < fullMelody.size() ; i++){
        int flag = true;
        for(int j = 0 ; j < targetVector.size() ; j++){
            if(fullMelody[i+j] != targetVector[j]){
                flag = false;
                break;
            }
        }
        if(flag){
            return true;
        }
    }
    return false;
}

int convert(string timeStr){
    int hour = stoi(timeStr.substr(0, 2));
    int minute = stoi(timeStr.substr(3, 2));
    
    return hour * 60 + minute;
}

vector<string> split(string k){
    vector<string> answer;
    istringstream ss(k);
    string buffer = "";
    while(getline(ss, buffer, ',')){
        answer.push_back(buffer);
    }
    return answer;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "(None)";
    int answerTime = 0;
    int answerStartTime = 0;
    string startTime, endTime, name, melody;
    for(int i = 0 ; i < musicinfos.size() ; i++){
        vector<string> temp = split(musicinfos[i]);
        startTime = temp[0];
        endTime = temp[1];
        name = temp[2];
        melody = temp[3];
        
        int startTimeInt = convert(startTime);
        int endTimeInt = convert(endTime);
        if(check(startTimeInt, endTimeInt, name, melody, m)){
            int gap = endTimeInt - startTimeInt;
            
            if(gap > answerTime){
                answer = name;
                answerTime = gap;
                answerStartTime = startTimeInt;
            }
            else if(gap == answerTime) {
                if(answerStartTime > startTimeInt){
                    answer = name;
                    answerStartTime = startTimeInt;
                }
            }
        }
    }
    
    return answer;
}

 

 

추가로, 다른 분들의 풀이를 봤는데 나처럼 멜로디를 vector에 저장하지 않고 string형태로 푸신 분들을 봤다.

그러면 string.find(원하는 값)으로 바로 찾을 수가 있는데, 그렇다면 아까 말한 ABC#에서 ABC도 통과하지 않나?

라는 생각이 들었다.

이 분들은 아예 C#을 다른 문자열로 치환해서 푸셨다.

즉 C#을 T라고 바꾸면 ABC#은 ABT가 되고 ABC는 통과하지 않는 것이다.

 

string.find를 사용할 수 있는 아주 좋은 풀이였다.