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

문제 설명

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금 그 곡' 서비스를 이용하곤 한다. 방금 그 곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

• 방금 그 곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
• 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
• 음악이 00:00을 넘겨서까지 재생되는 일은 없다.
• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
• 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

 

입력 형식

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

• m은 음 1개 이상 1439개 이하로 구성되어 있다.
• musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ', '로 구분된 문자열이다.
  • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
  • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
  • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

 

출력 형식

조건과 일치하는 음악 제목을 출력한다.

 

입출력 예

m	musicinfos	answer
"ABCDEFG"	["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"HELLO"
"CC#BCC#BCC#BCC#B"	["03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"]	"FOO"
"ABC"	["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"WORLD"

 

 

코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string del_hash(string &s)
{
    int i;
    string res = "";
    
    for (i = 0; i < s.size(); i++)
    {
        if (s[i + 1] == '#')
            res += tolower(s[i++]);
        else
            res += s[i];
    }
    return res;
}

int get_time(string &s)
{
    int h, m;
    int sh = stoi(s.substr(0, 2));
    int sm = stoi(s.substr(3, 2));
    int eh = stoi(s.substr(6, 2));
    int em = stoi(s.substr(9, 2));
    
    if (sm > em)
    {
        em += 60;
        eh -= 1;
    }
    h = eh - sh;
    m = em - sm;
    
    return (h * 60 + m);
}

string get_title(string &s)
{
    int i = 12;
    int size = 0;
    
    while (i < s.size() && s[i] != ',')
        i++;
    
    return s.substr(12, i - 12);
}

string get_melody(string &s)
{
    int i = 12;
    
    while (i < s.size() && s[i] != ',')
        i++;
    i++;
    
    return s.substr(i);
}

string solution(string m, vector<string> musicinfos) {
    string answer = "(None)";
    string melody;
    int i, res;
    int time, max_time = 0;
    
    m = del_hash(m);
    for (i = 0; i < musicinfos.size(); i++)
    {
        time = get_time(musicinfos[i]);
        if (time <= max_time)
        {
            continue;
        }
        melody.clear();
        melody += get_melody(musicinfos[i]);
        melody = del_hash(melody);
        while (melody.size() < time)
        {
            melody += melody;
        }
        melody = melody.substr(0, time);
        res = melody.find(m);
        if (res == string::npos)
        {
            continue;
        }
        max_time = time;
        answer.clear();
        answer += get_title(musicinfos[i]);
    }
    return answer;
}

 

음악과 악보에는 #이 붙은 음계가 포함되어 있다. 이 경우는 #이 붙지 않은 음계와 구분하기가 어렵기 때문에 소문자로 변환해준다. 예를 들어 C# -> c, D# -> d와 같이 변환된다. 이와 같은 변환은 del_hash() 함수가 수행한다.

모든 곡에 대해 for문 내부를 수행한다. 먼저 get_time() 함수를 통해 실행시간을 계산한다. 지금까지 찾은 조건이 일치하는 곡보다 실행시간이 짧거나 같은 경우는 확인하지 않는다. 

실행시간이 더 긴 경우에는 get_melody() 함수를 통해 악보를 읽어온다. 악보는 실행시간만큼 반복된다. 

• melody = melody.substr(0, time); 

테스트 케이스 30에서만 실패가 떴는데 위 코드를 추가하여 통과할 수 있었다.

melody를 완성하면 melody에서 m이 나타나는지 찾는다. 만약 나타나지 않는다면 다음 곡으로 넘어간다. m이 나타난 경우에는 max_time을 갱신하고, answer에 get_title() 함수로 구한 곡의 제목을 저장한다.

 

링크

programmers.co.kr/learn/courses/30/lessons/17683

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

github.com/inbdni/Programmers/blob/master/level02/%EB%B0%A9%EA%B8%88%EA%B7%B8%EA%B3%A1.cpp

inbdni/Programmers