[ 프로그래머스 [3차] 방금 그 곡 (Lv2) ] (C++)

프로그래머스의 방금 그 곡(Lv2) 문제이다.

[ 문제풀이 ]

문제를 분석하면서 우리가 알고 있어야 할 정보들부터 계산 과정에서 주의해야 할 것들, 그리고 최종적으로 정답 도출을 위한 방법을 순차적으로 알아보자.

#1 음 처리

만약, 주어지는 멜로디가 단순히 ABCDEFG 이렇게 7개의 문자였다면 문제가 훨씬 더 간단했을 수도 있을 것 같다.

그런데, 문제는 멜로디에 '#'이 들어가는 음계들이 있다는 것이다.

또한, '#'이 문자열 중 한 칸을 차지하고 있기 때문에, 이를 따로 처리하는 과정이 필요하다.

그래서 본인은,

C# = H , D# = I , F# = J , G# = K , A# = L 로 바꿔버렸다.

즉, 본인이 표현한 방식에서 12개의 음은, C D E F G A B H I J K L 이렇게 12개로 표현해 주었다.

이렇게 표현하면 '#'을 고려하지 않아도 되기 때문에 훨씬 더 간단하게 음을 표현할 수 있다.

#2 구해야 할 정보

우리는 네오가 기억한 멜로디와 일치하는 멜로디를 가진 곡을 찾아야 한다.

그런데, 조건이 일치하는 음악이 여러개일 때는 재생된 시간이 제일 긴 음악을, 그 또한 같을 경우에는 먼저 입력된 음악 제목을 반환해야 한다.

즉 ! 우리는 여기서

1. 음악이 재생된 시간

2. 음악이 입력된 순서

이 2가지 정보를 알아야 한다는 것을 알 수 있다.

먼저, 음악이 재생된 시간은 입력으로 HH : MM , HH : MM 형식으로 주어진다.

본인은 시와 분을 통일시키기 위해서 시를 분으로 맞춰주었다. 즉, Start HH : Start MM , End HH : End MM 으로 음악 재생시간이 주어졌다고 가정하면, 음악이 재생된 시간은 ( End HH * 60 + End MM ) - ( Start HH * 60 + Start MM ) 으로 구해주었다.

음악이 입력된 순서는 solution 함수의 매개변수로 주어지는 musicinfos의 인덱스 번호를 통해서 구해주었다.

또한, 이를 저장해 놓기 위해서 구조체를 하나 설정해주었다.

struct MUSIC 이라는 구조체를 선언해 주었는데, 이 구조체가 가지고 있는 멤버변수로는 { 음악 재생 시간 , 음악이 입력된 순서, 음악의 제목 } 이렇게 3개의 멤버변수를 설정해 주었다.

#3 음악의 음 처리하기

네오가 들은 음은 1번에서 설명한 '음 처리' 방식으로 바로 변환할 수가 있다.

그런데, 음악의 음은 바로 처리할 수가 없다.

다음과 같은 예시를 한번 보자.

예를 들어서 우리가 #2번 과정을 통해서 음악이 재생된 시간이 '4초' 라고 구했다고 가정해보자.

그런데, 주어진 음악의 음이 ABCDEF 라고 생각해보자.

그럼 ? 실질적으로 네오가 들은 음은 'ABCD' 밖에 되질 않는다. 왜냐하면, 음악이 4초밖에 재생이 되질 않았기 때문이다.

따라서, "음악이 재생된 시간동안, 해당 음악이 연주되는 음을 판단" 해주는 과정을 1차적으로 해주어야 한다.

또한, 예외적인 다음과 같은 경우 또한 처리해 주어야 한다.

음악이 재생된 시간이 4초이고, 음악의 음이 ABCD#EF 라고 가정해보자.

그럼, 네오가 들을 수 있는 음악의 음은 'ABCD#' 이렇게 4개의 음이 된다.

그런데 ! 만약, 4초라고 해서, 앞에서부터 4개의 문자만 판단한다면 ? 'ABCD'로 잘못 판단하는 경우가 발생할 수도 있다.

따라서, '#'이 마지막에 있는 경우 또한 따로 처리를 해 주어야 한다.

이렇게 음악이 재생된 시간동안, 해당 음악이 연주되는 음을 판단했다면, 이제 #1 과정을 통해서 다시 '#'을 없애는 과정을 진행하면 된다.

#4 정답 도출하기

#2에서 설명한 MUSIC이라는 구조체를 vector로 선언해 주었다.

그래서, 네오가 들었던 음과 일치하는 음악이라면, 이 Vector에 해당 음악의 정보들을 삽입해 주었다.

최종적으로는, 이 구조체 벡터를 조건에 맞게 정렬을 시켜주었고, 정렬 후 가장 앞에 있는 음악의 제목을 return 시켜 주었다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// C D E F G A B H I J K L
struct MUSIC
{
    int Play_Time;
    int Idx;
    string Name;
};
 
void Remake_Melody(string &S)
{
    /* 주어진 음에서 , '#'을 없애는 과정. */
    /* C# = H
       D# = I
       F# = J
       G# = K
       A# = L */
    string Result = "";
    for (int i = 0; i < S.length(); i++)
    {
        if (S[i] == '#') continue;
        if (i + 1 < S.length() && S[i + 1] == '#')
        {
            if (S[i] == 'C') Result += 'H';
            else if (S[i] == 'D') Result += 'I';
            else if (S[i] == 'F') Result += 'J';
            else if (S[i] == 'G') Result += 'K';
            else if (S[i] == 'A') Result += 'L';
        }
        else Result += S[i];
    }
    S = Result;
}
 
int Invert_Time(int Idx, int H, int HH, int M, int MM, vector<string> Music)
{
    /* 시간을 분으로 통일한 후, 전체 시간을 return 하는 함수. */
    /* HH * 60 + MM */
    string Hour = "";
    Hour += Music[Idx][H];
    Hour += Music[Idx][HH];
    int I_Hour = stoi(Hour);
    I_Hour *= 60;
 
    string Minute = "";
    Minute += Music[Idx][M];
    Minute += Music[Idx][MM];
    int I_Minute = stoi(Minute);
    
    return I_Hour + I_Minute;
}
 
bool Compare(string A, string B)
{
    /* 네오가 들은 Melody와 곡의 Melody가 일치하는지 판단하는 함수. */
    int Len = A.length();
    int Idx = 0;
    for (int i = 0; i < B.length(); i++)
    {
        if (B[i] == A[0])
        {
            int B_Idx = i;
            int A_Idx = 0;
            bool Flag = true;
            for (int i = 0; i < Len; i++)
            {
                if (B_Idx == B.length())
                {
                    Flag = false;
                    break;
                }
                if (B[B_Idx] != A[i])
                {
                    Flag = false;
                    break;
                }
                B_Idx++;
            }
            if (Flag == true) return true;
        }
    }
    return false;
}
 
bool Cmp(MUSIC A, MUSIC B)
{
    if (A.Play_Time >= B.Play_Time)
    {
        if (A.Play_Time == B.Play_Time)
        {
            if (A.Idx < B.Idx)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
}
 
string solution(string m, vector<string> musicinfos) 
{
    Remake_Melody(m);
    string answer = "";
    vector<MUSIC> Candidate;
    for (int i = 0; i < musicinfos.size(); i++)
    {
        /* 음악의 재생 시작시간과 종료시간을 통해서, 재생된 시간을 구한다. */
        int Start_Time = Invert_Time(i, 0, 1, 3, 4, musicinfos);
        int End_Time = Invert_Time(i, 6, 7, 9, 10, musicinfos);
        int Play_Time = End_Time - Start_Time;
        /**********************************************************/
 
        /* 곡이 재생된 시간을 바탕으로 , 실질적으로 곡이 재생된 음만 판단. */
        /* 올바르게 판단 후, 다시 '#'을 없애는 과정 진행. */
        string Name = "";
        int Melody_Idx = 12;
        for (; musicinfos[i][Melody_Idx] != ','; Melody_Idx++) Name += musicinfos[i][Melody_Idx];
        Melody_Idx++;
        int Start_Melody_Idx = Melody_Idx;
        
        string Melody = "";
        for (int j = 0; j < Play_Time; j++)
        {
            /* 멜로디를 하나씩 진행해 나가다가, 만약, 멜로디의 마지막까지 왔는데 재생시간이 남았다면 ?*/
            /* 다시 첫 부분으로 가서 반복. */
            /* 따라서, '첫 부분'을 Start_Melody_Idx에 저장해놓고 관리. */
            if (Melody_Idx == musicinfos[i].length()) Melody_Idx = Start_Melody_Idx;
 
            Melody += musicinfos[i][Melody_Idx];
            if (musicinfos[i][Melody_Idx] == '#') j--;
            Melody_Idx++;
        }
        if (musicinfos[i][Melody_Idx] == '#') Melody += '#';
        Remake_Melody(Melody);
        /**************************************************************/
 
        if (Compare(m, Melody) == true) Candidate.push_back({ Play_Time, i, Name });
    }
    if (Candidate.size() == 0) return "(None)";
    sort(Candidate.begin(), Candidate.end(), Cmp);
    return Candidate[0].Name;
}