[Programmers] 방금 그곡

안녕하세요. 이번 포스팅에서는 Programmers 방금 그 곡이라는 문제를 풀어보도록 하겠습니다.

 

해당 문제는

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

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

 

위 링크에서 확인하실 수 있습니다.

 

우선... 이 문제가 문자열 + 구현인데, #이 붙어서 굉장히 복잡했습니다.

 

결과적으로 깡으로 구현하는것을 성공하긴 했습니다만... 코드를 보시면 이게 좋지 않다는 것을 아실 겁니다.

 

#include <bits/stdc++.h>
using namespace std;
vector<pair<string, pair<int,int>>> res;
int toTime(string _time) {
    int hour = stoi(_time.substr(0,2));
    int min = stoi(_time.substr(3, 2));
    return hour*60+min;
}
void parsing(string toFind, string music, int idx) {
    int startTime = toTime(music.substr(0, 5));
    int endTime = toTime(music.substr(6, 5));
    music = music.substr(12);

    int comma = music.find(",");
    string musicName = music.substr(0, comma);
    string melody = music.substr(comma+1, music.size()-comma-1);

    int runningTime = endTime - startTime;
    vector<string> playMelody, findMelody;

    int t = 0, _idx=0;
    while(t < runningTime) {
        string _m = ""; _m += melody[(_idx)%(melody.size())];
        if(_m == "#") playMelody[playMelody.size()-1] += '#';
        else playMelody.push_back(_m), t++;
        _idx++;
    }
    string _m = ""; _m += melody[(_idx)%(melody.size())];
    if(_m == "#") playMelody[playMelody.size()-1] += '#';

    for(int i = 0; i < toFind.size(); i++) {
        string _m = ""; _m+=toFind[i];
        if(_m == "#") findMelody[findMelody.size()-1]+='#';
        else findMelody.push_back(_m);
    }

    if (findMelody.size() > playMelody.size()) return;
    for(int i = 0; i <= playMelody.size()-findMelody.size(); i++) {
        string nextword = "";
        for(int j = i; j < i+findMelody.size(); j++) nextword += playMelody[j];
        if(nextword == toFind) { res.push_back({musicName, {runningTime, idx}}); break; } //break; 
    }
}
bool cmp(pair<string, pair<int,int>>& a, pair<string, pair<int,int>>& b) {
    if(a.second.first != b.second.first) return a.second.first > b.second.first;
    return a.second.second < b.second.second;
}
string solution(string m, vector<string> musicinfos) {
    string answer = "";
    for(int i = 0; i < musicinfos.size(); i++) parsing(m, musicinfos[i], i);
    if(res.size() == 0) return "(None)";
    sort(res.begin(), res.end(), cmp);
    answer = res[0].first;
    return answer;
}

 

정말 깡으로 분리해서 벡터에 각각 저장한 뒤, 비교했습니다.

 

1. 카카오 코딩 테스트에서 "HH:MM"식의 시간 표현이 많이 나옵니다. 이러한 형식은 보통 가장 작은 시간 단위로 변경하셔서 푸시는 것이 좋습니다.

 

2. 결괏값에 정렬 조건이 있습니다. 정렬 조건을 확인하시기 위해 여러 테스트 케이스를 직접 넣어보셔야 합니다.

 

3. #붙은 음계를 소문자로 바꿔서 표현할 수 있습니다.

이 문제에서 예외 케이스가 많이 발생하고, 코드가 더러워지는 이유 중에 하나가 # 처리인데요. 이게 문자열에 대한 메서드가 적은 c++에서는 예쁘게 처리하기가 어렵습니다. 따라서 적절하게 C# -> c와 같이 소문자로 치환하셔서 해결하시면 더 구현이 용이합니다.

 

아래는 수정된 코드입니다.

#include <bits/stdc++.h>
using namespace std;

vector<pair<string, pair<int,int>>> v;
int toTime(string time) {
    string hour = time.substr(0,2);
    string min = time.substr(3,2);
    return stoi(hour)*60 + stoi(min);
}
string tokenize(string s) {
    string ret = "";
    for(int i = 0; i < s.size(); i++) {
        if(s[i] == '#') {
            ret[ret.size()-1] = ret[ret.size()-1]-'A'+'a';  
        } else ret += s[i];
    }
    return ret;
}
void parsing(string m, string musicinfo, int infoIdx) {
    int startTime = toTime(musicinfo.substr(0,5));
    int endTime = toTime(musicinfo.substr(6,5));
    int runningTime = endTime - startTime;
    
    musicinfo = musicinfo.substr(12);
    
    int comma = musicinfo.find(",");
    string infoName = musicinfo.substr(0, comma);
    string melody = musicinfo.substr(comma+1, musicinfo.size()-comma-1);
    melody = tokenize(melody);
    string playMelody = "";
    for(int i = 0; i < runningTime; i++) playMelody += melody[i%melody.size()];
    if(m.size() > playMelody.size()) return;
    
    for(int i = 0; i <= playMelody.size()-m.size(); i++) {
        string next = playMelody.substr(i, m.size());
        if(next == m) {
            v.push_back({infoName, {runningTime, infoIdx}});
            break;
        }
    }
}
bool cmp(pair<string, pair<int,int>>& a, pair<string, pair<int,int>>& b) {
    if(a.second.first != b.second.first) return a.second.first > b.second.first;
    return a.second.second < b.second.second;
}
string solution(string m, vector<string> musicinfos) {
    string answer = "";
    string _m = tokenize(m);
    for(int i = 0; i < musicinfos.size(); i++) parsing(_m, musicinfos[i], i);
    if(v.size() == 0) return "(None)";
    
    sort(v.begin(), v.end(), cmp);
    answer = v[0].first;
    return answer;
}

 

실제로 코드의 길이는 큰 차이가 없어도, 디버깅하기도 훨씬 쉽고, #예외처리도 미리 하고 시작하기 때문에 실제 시험장에서 훨씬 유용한 접근 방법입니다.

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.