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

문제

 

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

프로그래머스

 

문제풀이

 

문제가 생각보다 복잡해 보이지만 복잡하게 생각 안 하면 풀만한 문제였다.

재생된 음악에서 m을 찾는 문제이다.

 

재생된 시간보다 악보다 짧다면 해당 악보를 여러 번 반복했다는 의미이다.

단순히 생각하면 재생된 시간에 맞춰 악보를 여러 번 나열하면 된다.

 

악보에 사용되는 음중에서 '#'이 붙은 음중 A#, C#, D#, F#, G#, 이렇게 5가지가 있다.

2글자여도 한음이므로 '#'이 붙은 모든 음을 치환하는 것이 문제 푸는 데에 있어서 편하다.

조건이 일치하는 음악이 여러 개일 때는 가장 긴 음악을 반환하고, 일치하는 음악이 없을 때는 (None)을 반환한다.

 

musicinfos를 음악 재생 시간을 기준으로 두고 내림차순으로 정렬한다.

-> m과 musicinfos의 음악을 탐색하면서 모두 '#'을 다른 알파벳으로 치환한다.

-> musicinfos[idx]를 파싱 하여 start, end, name, sheet으로 나눈다.

-> 음악 재생시간이 악보길이보다 짧다면 악보 끝을 제거한다. (악보길이를 음악 재생시간과 같게 맞춘다)

-> 악보길이가 음악시간보다 짧다면 악보를 이어 붙인다.

-> find함수를 통해 악보에서 m을 찾는다.

--> 같다면 해당 곡 이름을 return, 다르다면 다음 musicinfos[idx]를 탐색한다.

 

조건에 맞는 음악이 없다면 "(None)"을 return 한다.

 

bool cmp(const string& s1, const string& s2) {
    int s1_start = stoi(s1.substr(0, 2)) * 60 + stoi(s1.substr(3, 2));
    int s1_end = stoi(s1.substr(6, 2)) * 60 + stoi(s1.substr(9, 2));

    int s2_start = stoi(s2.substr(0, 2)) * 60 + stoi(s2.substr(3, 2));
    int s2_end = stoi(s2.substr(6, 2)) * 60 + stoi(s2.substr(9, 2));

    return s1_end - s1_start > s2_end - s2_start;
}

musicinfos를 내림차순으로 정렬하기 위한 cmp함수이다.

substr로 해당 string의 부분문자열을 구한다.

두 음악 시작시간과 종료시간을 구해 더 길이가 긴 음악이 앞쪽(왼쪽)으로 가게끔 정렬을 하는 역할을 한다.

 

int get_music_play_time(string& start, string& end) {
    int m_start = stoi(start.substr(0, 2)) * 60 + stoi(start.substr(3, 2));
    int m_end = stoi(end.substr(0, 2)) * 60 + stoi(end.substr(3, 2));

    return m_end - m_start;
}

해당 음악의 실행시간을 구하는 함수이다.

string형인 start와 end을 인자로 받아 substr를 통하여 분으로 모두 바꾼 후 종료시간에서 시작시간을 뺀 값을 return 한다.

 

string replace_sharp(string& s, string origin, string change) {
    int pos(0);
    while ((pos = s.find(origin, pos)) != -1)
        s.replace(pos, 2, change);

    return s;
}

string replace_all(string& s) {
    s = replace_sharp(s, "A#", "a");
    s = replace_sharp(s, "C#", "c");
    s = replace_sharp(s, "D#", "d");
    s = replace_sharp(s, "F#", "f");
    s = replace_sharp(s, "G#", "g");

    return s;
}

'#'이 붙은 음을 모두 바꾸기 위한 replace_all 함수이다.

replace_sharp을 통해 s의 "A#"을 "a"로, "C#"을 "c"로, "D#"을 "d"로, "F#"을 "f"로, "G#"을 "g"로 바꾼다.

 

replace_sharp함수는 탐색할 문자 s, 바꿀 원본 문자열, origin, 바꿀 문자열 change를 인자로 받는다.

find함수를 통해 origin을 찾고 change로 바꾼다.

 

 

string solution(string m, vector<string> musicinfos) {
    string answer = "";
    stable_sort(musicinfos.begin(), musicinfos.end(), cmp);

    m = replace_all(m);

    for (int idx = 0; idx < musicinfos.size(); ++idx) {
        string info = musicinfos[idx];
        info = replace_all(info);

        istringstream iss(info);
        vector<string>parsing;
        string substr("");

        string start(""), end(""), name(""), sheet("");

        while (getline(iss, substr, ',')) {
            parsing.push_back(substr);
        }

        start = parsing[0], end = parsing[1], name = parsing[2], sheet = parsing[3];

        int music_time = get_music_play_time(start, end);

        if (music_time < sheet.size()) {
            sheet.erase(music_time);
        }

        while (sheet.size() < music_time) {
            sheet += sheet;
        }
        
        if (music_time < sheet.size()) {
            sheet.erase(music_time);
        }

        if (sheet.find(m) != -1) return name;
    }

    return "(None)";
}

 

 

조건에 일치하는 음악이 여러개면 재생 시간이 긴 음악,

재생 시간이 같을 경우 먼저 입력된 음악이 답이 된다.

따라서 stable_sort를 이용하여 재생 시간을 기준으로 내림차순 한다.

 

파싱 하기 위해 vector <string>parsing과 istringstream을 이용하였다.

musicinofs[idx]를 replace_all을 통해 '#'이 붙은 음을 모두 바꾼다.

','을 구분자로 두어 문자열을 파싱 한다.

파싱 한 문자열을 start, end, name, sheet로 저장한다.

get_music_play_time을 통해 음악 재생 시간을 구한다.

 

만약, 음악 재생 시간 < 악보길이라면 악보의 뒷부분을 제거한다.

 

만약, 악보길이 < 음악 재생 시간이라면 악보를 이어 붙인다.

이 경우 악보길이가 음악 재생 시간을 넘어갈 수 있으므로 추가로 조건을 두어 음악 재생 시간만큼의 길이를 갖도록 한다.

 

find함수를 통해 해당 악보에서 m을 찾았다면 정답이므로 바로 음악의 이름인 name을 return 한다.

찾지 못했다면 다음 음악을 탐색한다.

 

모든 음악을 탐색해도 정답이 없다면 "(None)"을 return 한다.

 

 

 

 

코드

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

bool cmp(const string& s1, const string& s2) {
    int s1_start = stoi(s1.substr(0, 2)) * 60 + stoi(s1.substr(3, 2));
    int s1_end = stoi(s1.substr(6, 2)) * 60 + stoi(s1.substr(9, 2));

    int s2_start = stoi(s2.substr(0, 2)) * 60 + stoi(s2.substr(3, 2));
    int s2_end = stoi(s2.substr(6, 2)) * 60 + stoi(s2.substr(9, 2));

    return s1_end - s1_start > s2_end - s2_start;
}

int get_music_play_time(string& start, string& end) {
    int m_start = stoi(start.substr(0, 2)) * 60 + stoi(start.substr(3, 2));
    int m_end = stoi(end.substr(0, 2)) * 60 + stoi(end.substr(3, 2));

    return m_end - m_start;
}

string replace_sharp(string& s, string origin, string change) {
    int pos(0);
    while ((pos = s.find(origin, pos)) != -1)
        s.replace(pos, 2, change);

    return s;
}

string replace_all(string& s) {
    s = replace_sharp(s, "A#", "a");
    s = replace_sharp(s, "C#", "c");
    s = replace_sharp(s, "D#", "d");
    s = replace_sharp(s, "F#", "f");
    s = replace_sharp(s, "G#", "g");

    return s;
}


string solution(string m, vector<string> musicinfos) {
    string answer = "";
    stable_sort(musicinfos.begin(), musicinfos.end(), cmp);

    m = replace_all(m);

    for (int idx = 0; idx < musicinfos.size(); ++idx) {
        string info = musicinfos[idx];
        info = replace_all(info);

        istringstream iss(info);
        vector<string>parsing;
        string substr("");

        string start(""), end(""), name(""), sheet("");

        while (getline(iss, substr, ',')) {
            parsing.push_back(substr);
        }

        start = parsing[0], end = parsing[1], name = parsing[2], sheet = parsing[3];

        int music_time = get_music_play_time(start, end);

        if (music_time < sheet.size()) {
            sheet.erase(music_time);
        }

        while (sheet.size() < music_time) {
            sheet += sheet;
        }

        if (music_time < sheet.size()) {
            sheet.erase(music_time);
        }

        if (sheet.find(m) != -1) return name;
    }

    return "(None)";
}