프로그래머스 - [3차] 방금그곡 (Lv.2)

문제 링크

• 👉 방금그곡

문제 설명

• C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개의 음이 있다.
• 라디오에서 틀어주는 노래의 시작시간, 종료시간, 악보 정보가 담긴 배열이 주어진다.
• 노래의 재생시간동안 악보의 처음부터 반복된다. 만약, 재생시간이 더 길다면 노래가 처음부터 다시 반복된다. 재생시간이 악보보다 짧다면 끊기는 것까지 나온다.
• 네오가 기억하는 멜로디가 주어질 때, 라디오에서 흘러나온 노래 중 해당 멜로디가 포함된 노래의 제목을 반환하라.
• 만약 여러가지가 있다면 라디오에서 가장 오랫동안 재생된 노래 제목을 반환하라.
• 이것마저 여러가지가 있다면 가장 먼저 들어온 노래 제목을 반환하라.

문제 접근

• stringstream 을 이용해서 주어진 노래 정보를 파싱한다.
• 노래제목, 총 재생시간, 들어온 시간 을 담는 구조체로 노래 정보를 처리한다.
• 멜로디 음 중에서 #을 포함하는 음이 있으므로 이를 치환해주어야 데이터를 처리하는데 까다롭지 않다. 따라서, C#, D#, F#, G#, A# 을 모두 소문자 알파벳으로 치환한다.
• 총 재생시간에 대해서 노래의 멜로디를 기록하고, 부분문자열을 찾는 메서드를 활용해서 네오가 기억하는 멜로디가 존재하는지 찾는다.

구현(All Pass)

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

using namespace std;

typedef struct _music{
    string name;
    int playTime;
    int index;
} Music;

string parsing(Music& imusic, string musicInfo, int index){
    stringstream stm(musicInfo);
    string name, sheet, stime, etime, hour, min;
    int playTime = 0;
    string token;
    int cnt = 0;
    while(getline(stm, token, ',')){
        if(cnt==0) stime = token;
        else if(cnt==1) etime = token;
        else if(cnt==2) name = token;
        else if(cnt==3) sheet = token;
        cnt++;
    }
    
    // get play time
    stm.clear(); stm.str(etime); cnt=0;
    while(getline(stm, token, ':')){
        if(cnt==0) hour = token;
        else if(cnt==1) min = token;
        cnt++;
    }
    playTime = stoi(hour)*60 + stoi(min);
    stm.clear(); stm.str(stime); cnt=0;
    while(getline(stm, token, ':')){
        if(cnt==0) hour = token;
        else if(cnt==1) min = token;
        cnt++;
    }
    playTime -= (stoi(hour)*60+stoi(min));
    
    imusic = {name, playTime, index};
    
    return sheet;
}

string replaceSheet(string sheet){
    string ret;
    for(int i=0; i<sheet.length(); i++){
        if(sheet[i]=='#'){
            char ch = ret.back();
            ret.pop_back();
            ret.push_back(tolower(ch));
        }
        else
            ret.push_back(sheet[i]);
    }
    return ret;
}

bool checkMemory(string m, string sheet, int playTime){
    int len = sheet.length();
    int idx = 0;
    string cstr;
    for(int t=0; t<playTime; t++){
        if(idx==len) idx=0;
        cstr.push_back(sheet[idx++]);
    }
    // cout << cstr << endl;
    if(cstr.find(m)==string::npos) return false;
    return true;
}

bool cmp(Music m1, Music m2){
    if(m1.playTime != m2.playTime)
        return m1.playTime > m2.playTime;
    else
        return m1.index < m2.index;
}

string solution(string m, vector<string> musicinfos) {
    string answer = "";
    
    m = replaceSheet(m);
    // cout << "memory: " << m << endl;
    string sheet;
    Music music;
    vector<Music> cand;
    for(int i=0; i<musicinfos.size(); i++){
        sheet = parsing(music, musicinfos[i], i); // 악보 반환
        sheet = replaceSheet(sheet);
        // cout << sheet << endl;
        if(checkMemory(m, sheet, music.playTime)){
            cand.push_back(music);
        }
    }
    if(cand.size()==0) answer = "(None)";
    else {
        sort(cand.begin(), cand.end(), cmp);
        answer = cand[0].name;
    }
    
    return answer;
}

• str.substr(target) 은 str 에서 target 부분 문자열이 있는지 찾고, 있다면 해당 문자열의 첫번째 자리를 가리키는 반복자를 반환한다.
• 찾고자 하는 문자열이 없는 경우 string::npos 를 반환한다.