[ 프로그래머스 / 문자열 ] [3차] 방금그곡도움말 (KaKao)

1. 문제

---

 

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

 

 

2. 소스코드

---

- 이 문제에서 생각해야할 점은

 C#, D#과 같은 2byte를 차지하는 문자열을 어떻게 처리할 것인가?

 인거 같다.

 

- C#, D# 등 을 사용하지 않는 음인 c, d 등으로 치환해서 문제를 풀었다.

- 로직은 아래와 같다.

1) 곡의 총 재생시간을 구한다.

2) 재생 시간에 따른, 총 재생음 문자열을 구한다. (악보가 ABC이고 시간이 5라면 총 재생음은 ABCAB 이다)

3) 총 재생음에 기억한 음이 포함되는지 확인한다. 포함된다면 재생시간, 곡명을 정답에 추가한다.

4) 조건에 알맞게 정답을 출력한다.

 

- 차분히 구현하면 평이한 문제인것 같다.

- 문자열 비교에는 find를 사용했는데, KMP 알고리즘을 사용하는게 훨씬 효율적이다.

 

 

소스코드

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

using namespace std;

string conv(string notes) {
    int size = notes.size();
    string conv_str = "";
    for (int i = 0; i < size - 1; ++i) {
        if (notes[i] == '#') continue;
        if (notes[i + 1] != '#') conv_str += notes[i];
        else if (notes[i] == 'C') conv_str += 'c';
        else if (notes[i] == 'D') conv_str += 'd';
        else if (notes[i] == 'F') conv_str += 'f';
        else if (notes[i] == 'G') conv_str += 'g';
        else if (notes[i] == 'A') conv_str += 'a';
    }
    if (notes[size - 1] != '#') conv_str += notes[size - 1];
    return conv_str;
}

int getPlayTime(string s_time, string e_time) {
    int start_h = stoi(s_time.substr(0, 2));
    int start_m = stoi(s_time.substr(3, 2));
    int end_h = stoi(e_time.substr(0, 2));
    int end_m = stoi(e_time.substr(3, 2));
    return (end_h - start_h) * 60 + (end_m - start_m);
}
string solution(string m, vector<string> musicinfos) {
    vector<pair<int, string>> answer;
    m = conv(m);
    int size = musicinfos.size();
    for (int i = 0; i < size; ++i) {
        stringstream st(musicinfos[i]);
        string s_time, end_time, name, notes;
        getline(st, s_time, ',');
        getline(st, end_time, ',');
        getline(st, name, ',');
        getline(st, notes, ',');
        // 1) 총 재생 시간을 구한다.
        int time = getPlayTime(s_time, end_time);
        // 2) 재생 시간에 따른 총 재생음을 구한다.
        notes = conv(notes);
        string total = "";
        for (int j = 0, idx = 0; j < time; ++j) {
            total += notes[idx++];
            if (idx >= notes.size()) idx = 0;
        }
        // 3) 기억한 음이 포함되는지 확인한다. 포함된다면, 노래와 시간을 저장한다.
        if (total.find(m) != -1) answer.push_back({ time, name });
    }

    // 4) 조건에 맞는 정답을 출력한다.
    if (answer.size() == 0) return "(None)";
    else if (answer.size() == 1) return answer[0].second;
    else {
        int max_time = 0, max_idx;
        for (int i = 0; i < answer.size(); ++i) {
            if (answer[i].first > max_time) {
                max_time = answer[i].first;
                max_idx = i;
            }
        }
        return answer[max_idx].second;
    }
}