프로그래머스 - [3차] 방금그곡 [C++]

이 문제는 kmp 알고리즘 및 문자열, 구현 문제이다.

 

문제를 단순화하면 라디오에서 재생된 만큼의 음표 문자열에서 내가 들은 문자열을 각각 탐색하는 문제이다.

 

아주 단순하게, 브루트포스 알고리즘으로 문자열 탐색을 수행할 경우 O(NM)의 시간이 걸린다. 입력 문자열의 최대 길이가 1,439 이므로 단순하게 제곱하면 약 200만이고, 이를 최대 길이 100인 문자열 배열에 대해 수행해야 하므로 약 2억번의 연산이 걸려 1초 안에 풀 수 없게 된다.

 

그러므로 문자열 탐색 시간을 줄여아 하고 이 때 kmp 알고리즘이 떠올랐다. O(N + M) 시간에 탐색이 가능하므로 시간 안에 풀 수 있게 된다.

 

이 문제에서 핵심 포인트가 몇개 있는데 그 중 하나는 #이 붙은 음표이다. C#은 하나의 문자로 취급되어야 하기 때문에 전처리 과정이 필요하다. 나는 C#은 H, D#은 I 등 다른 문자를 부여하여 단순화하였다.

 

두번째로 kmp 알고리즘을 실제로 구현해야하는데, 여기서 생각이 안나 예전에 내가 정리했던 kmp 알고리즘을 참고해서 문제를 풀 수 있었다. 한번씩 잊을만하면 kmp가 나오기 때문에 항상 기억하고 있어야겠다.

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

using namespace std;

string convertSharp(const string& input) {
    const int inputSize = input.size();
    stack<char> st;
    
    for (int i = 0; i < inputSize; i++) {
        const char c = input[i];
        
        if (c == '#') {
            const char prev = st.top();
            st.pop();
            
            if (prev == 'C') {
                st.push('H');
            }
            else if (prev == 'D') {
                st.push('I');
            }
            else if (prev == 'F') {
                st.push('J');
            }
            else if (prev == 'G') {
                st.push('K');
            }
            else if (prev == 'A') {
                st.push('L');
            }
        }
        else {
            st.push(c);
        }
    }
    
    string result = "";
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    
    return result;
}

vector<string> split(const string& input, const char delimit) {
    vector<string> results;
    stringstream ss(input);
    string temp;
    
    while (getline(ss, temp, delimit)) {
        results.push_back(temp);
    }
    
    return results;
}

int countMinute(const string& startTime, const string& endTime) {
    vector<string> start = split(startTime, ':');
    vector<string> end = split(endTime, ':');
    
    const int endMinute = stoi(end[0]) * 60 + stoi(end[1]);
    const int startMinute = stoi(start[0]) * 60 + stoi(start[1]);

    return endMinute - startMinute;
}

string makeMusic(const int minutes, const string& sheet) {
    string result = "";
    
    const int sheetSize = sheet.size();
    int index = 0;
    
    for (int i = 0; i < minutes; i++) {
        result += sheet[index++];
        index %= sheetSize;
    }
    
    return result;
}

vector<int> makePi(const string& toFind) {
    const int findSize = toFind.size();
    
    vector<int> results(findSize, 0);
    
    int start = 1;
    int matched = 0;
    
    while (start + matched < findSize) {
        if (toFind[start + matched] == toFind[matched]) {
            matched++;
            results[start + matched - 1] = matched;
        }
        else {
            if (matched == 0) {
                start++;
            }
            else {
                start += matched - results[matched - 1];
                matched = results[matched - 1];
            }
        }
    }
    
    return results;
}

bool kmp(const string& longText, const string& toFind) {
    vector<int> pi = makePi(toFind);
    int start = 0; 
    int matched = 0;
    
    const int longSize = longText.size();
    const int findSize = toFind.size();
    
    while (start <= longSize - findSize) {
        if (matched < findSize && longText[start + matched] == toFind[matched]) {
            matched++;
            
            if (matched == findSize) {
                return true;
            }
        }
        else {
            if (matched == 0) {
                start++;
            }
            else {
                start += matched - pi[matched - 1];
                matched = pi[matched - 1];
            }
        }
    }
    
    return false;
}

string solution(string m, vector<string> musicinfos) {
    const string memory = convertSharp(m);
    
    int longMinute = -1;
    string answer = "(None)";
    
    for (string& input : musicinfos) {
        vector<string> infos = split(input, ',');
        
        const string startTime = infos[0];
        const string endTime = infos[1];
        const string title = infos[2];
        const string sheet = convertSharp(infos[3]);
        
        const int minutes = countMinute(startTime, endTime);
        
        const string music = makeMusic(minutes, sheet);
        
        if (kmp(music, memory)) {
            if (minutes > longMinute) {
                answer = title;
                longMinute = minutes;
            }
        }
    }
    
    return answer;
}