프로그래머스 - 2018 KAKAO BLIND RECRUITMENT[3차] 방금그곡

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

프로그래머스

 

시간을 정말 빡세게 잡았다면, 은근 귀찮은 파싱과 KMP나 라빈-카프 알고리즘을 사용해야했을 것이다.

 

하지만 이 문제는 그런 고급 문자열 검색 알고리즘까지 요구하진 않을것이다.

 

다만 C#, G# 같은 단어를 하나의 단어로 치환해주는 작업이 필요하다. 

 

그런데 만약 여기서 음악이 나오는 시간을 00:00~23.59 라고 하면, 23 * 60 + 59 = 2,070,721 이고 이것을 O(N^2) 하면 약 4조이다. 그래서 곧이 곧대로 시간대로 음악을 만들면 안된다.

 

난 여기서 찾는 음율의 길이 * 음악의 길이까지 진행했다. 이러면 충분히 길고 최악의 경우 찾는 음율의 길이와 음악의 길이가 1439로 같고 마지막 부분만 다를 경우다.

즉 다음과 같다.

 

기억하는 음율 : AA..AA

실제 음악 : AA..AB

 

이러면 1439 * 1439 의 시간 복잡도를 갖는다. 그리고 정렬을 다시 정의해주면 된다. 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct music{
    int musicTime;
    int idx;
    string name;
};
vector<string> splitInfo(string musicInfo){
    string tmp = "";
    vector<string> res;
    for(int i = 0; i < musicInfo.size(); i++){
        if(musicInfo[i] == ','){
            res.push_back(tmp);
            tmp = "";
        }else{
            tmp += musicInfo[i];
        }
    }
    res.push_back(tmp);
    
    return res;
}

vector<string> splitTime(string musicInfo){
    string tmp = "";
    vector<string> res;
    for(int i = 0; i < musicInfo.size(); i++){
        if(musicInfo[i] == ':'){
            res.push_back(tmp);
            tmp = "";
        }else{
            tmp += musicInfo[i];
        }
    }
    res.push_back(tmp);
    
    return res;
}

int calTime(string a, string b){
    int min_a, min_b, sec_a, sec_b;
    string tmp;
    vector<string> A = splitTime(a);
    vector<string> B = splitTime(b);
    min_a = stoi(A[0]);
    sec_a = stoi(A[1]);
    
    min_b = stoi(B[0]);
    sec_b = stoi(B[1]);
    
    return (min_b - min_a) * 60 + sec_b - sec_a;
}

string init(string m){
    string tmp = "";
    for(int i = 0; i < m.size(); i++){
        if(m[i] == 'A'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('0');
            }else{
                tmp.push_back(m[i]);
            }
        } 
        else if(m[i] == 'C'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('1');
            }else{
                tmp.push_back(m[i]);
            }
        }
        else if(m[i] == 'D'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('2');
            }else{
                tmp.push_back(m[i]);
            }
        }
        else if(m[i] == 'F'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('3');
            }else{
                tmp.push_back(m[i]);
            }
        }
        else if(m[i] == 'G'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('4');
            }else{
                tmp.push_back(m[i]);
            }
        }else if(m[i] == 'B'){
            if(i != m.size() - 1 && m[i + 1] == '#'){
                i++;
                tmp.push_back('5');
            }else{
                tmp.push_back(m[i]);
            }
        }else{
            tmp.push_back(m[i]);
        }
    }
    
    return tmp;
}

bool comp(music a, music b){
    if(a.musicTime == b.musicTime) return a.idx < b.idx;
    else return a.musicTime > b.musicTime;
}

string solution(string m, vector<string> musicinfos) {
    m = init(m);
    for(int i = 0; i < musicinfos.size(); i++) {
        musicinfos[i] = init(musicinfos[i]);
    }
    string answer = "";
    vector<music> ansList;
    for(int i = 0; i < musicinfos.size(); i++){
        vector<string> info = splitInfo(musicinfos[i]);
        string startTime = info[0];
        string endTime = info[1];
        string name = info[2];
        string melody = info[3];
        
        int musicTime = calTime(startTime, endTime);
        
        string musicMel = "";
 
        for(int i = 0; ; i++){            
            musicMel.push_back(melody[i % melody.size()]);
            
            if(i == m.size() * melody.size()) break;
            if(i == musicTime - 1) break;
        }
        
        for(int i = 0; i < musicMel.size(); i++){
            bool flag = true;
           if(musicMel[i] == m[0]){
               for(int j = i; j < m.size() + i; j++){
                   if(musicMel[j] != m[j - i]){
                       flag = false;
                       break;
                   }
               }
            if(flag == true) {
                ansList.push_back({musicTime, i, name});
                break;
            }
           }
        }
    }
    
    sort(ansList.begin(), ansList.end(), comp);
    
    if(ansList.size() == 0) return "(None)";
    else return ansList[0].name;
}