Programmers - 방금그곡

---

title: Programmers - 방금그곡
date: 2022-07-14
tags:

• Algorithm

---

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

문제 요약

특정 멜로디를 들었고, 음악의 길이와 악보가 주어진다. 여러 음악과 일치하면 길이가 가장 긴 음악, 길이가 같다면 먼저 입력된 음악이 정답이다.
음악의 제목, 혹은 아무 음악과도 일치하지 않으면 "(None)"을 return한다.

문제 풀이

카카오답게 정말 귀찮은 문제이다.
우선 기억한 멜로디는 음악의 일부분과 정확하게 일치하여야 한다. 이 것이 매우 중요하다.
음악을 길이에 맞추어 악보를 구성하고, 악보의 일부가 멜로디와 일치하는지 확인하는 작업을 거치면 된다.
악보의 길이보다 재생 시간이 길다면 악보를 반복하며, 재생 시간이 짧다면 해당 시간만큼만 악보를 자르면 된다.

풀이 자체는 간단하나, 삽질을 많이 하였다.

1. 기억한 멜로디를 반복되는 구간을 찾아 잘라서 사용하였다.
   멜로디의 반복은 음악의 반복이라 생각하였다. 이는 맞을 수도 있지만, 멜로디의 일부분과 음악이 일치할 가능성이 존재한다.
   또한, 멜로디가 온전하게 음악의 일부에 포함되어야 한다. 결국 반복되는 구간을 자르더라도 사용할 부분이 없다는 것이다.

2. '#' 삭제 처리를 안 하였다.
   5개 음에 #이 붙어있으며, string으로 주어졌다.
   하나의 음이 두 바이트를 차지하였고, 결국 이는 음악의 길이를 잘못 측정하여 문제를 풀 수 없게 만들었다.
   결국 #이 발견될 경우 앞의 문자를 바꾸어주고, #을 제외한 두 부분을 합치는 방식으로 해결하였다.

이 외에도 작은 삽질을 많이 하였다.
문제를 풀며 다시 한 번 느낀 것은 문제를 이해하고, 문제의 조건을 정확하게 써 놓아야 문제를 가장 빠르고 정확하게 풀 수 있다는 것이다.

프로그램

#include <string>
#include <vector>
#include <utility>

using std :: vector ;
using std :: string ;
using std :: pair ;
using std :: make_pair ;

string eraseSharp ( string strTarget )
{
    int iStrSize = strTarget.size () ;



    for ( int i = 1 ; i < iStrSize ; ++i )
    {
        if ( '#' == strTarget [ i ] )
        {
            strTarget [ i - 1 ] += 7 ;
            strTarget = strTarget.substr ( 0 , i ) + strTarget.substr ( i + 1 , iStrSize - i - 1 ) ;
            -- iStrSize ;
        }
    }

    return strTarget ;
}

pair < string , pair < int , string > > pGetMusicInfo ( string strMusic )
{
    int iIndex = 0 ;
    int iMusicStart = ( strMusic [ 0 ] - '0' ) * 600 + ( strMusic [ 1 ] - '0' ) * 60 + ( strMusic [ 3 ] - '0' ) * 10 + ( strMusic [ 4 ] - '0' ) ;
    int iMusicEnd = ( strMusic [ 6 ] - '0' ) * 600 + ( strMusic [ 7 ] - '0' ) * 60 + ( strMusic [ 9 ] - '0' ) * 10 + ( strMusic [ 10 ] - '0' ) ;
    int iMusicLen = iMusicEnd - iMusicStart ;



    if ( iMusicLen < 0 )
        iMusicLen += 1440 ;

    for ( iIndex = 12 ; iIndex < strMusic.size () ; ++ iIndex )
    {
        if ( ',' == strMusic [ iIndex ] )
            break ;
    }

    string strName = strMusic.substr ( 12 , iIndex - 12 ) ;
    ++ iIndex ;
    string strTemp = eraseSharp ( strMusic.substr ( iIndex , strMusic.size () - iIndex ) ) ;
    string strSheet = "" ;

    for ( int i = 0 ; i < ( iMusicLen / strTemp.size () ) ; ++i )
    {
        strSheet += strTemp ;
    }
    strSheet += strTemp.substr ( 0 , iMusicLen % strTemp.size () ) ;

    return { strName , { iMusicLen , strSheet } } ;
}

string solution ( string m , vector < string > musicinfos )
{
    string strInput = eraseSharp ( m ) ;
    int iInputSize = eraseSharp ( strInput ).size () ;
    int iMusicSize = musicinfos.size () ;
    pair < string , int > pAnswer ;                // Music name , length



    pAnswer.first = "" ;
    pAnswer.second = -1 ;

    for ( int i = 0 ; i < iMusicSize ; ++i )
    {
        pair < string , pair < int , string > > pTemp = pGetMusicInfo ( musicinfos [ i ] ) ;    // Music name , length , sheet

        if ( ( pTemp.second.first < iInputSize ) || ( pTemp.second.first < pAnswer.second ) )
            continue ;

        for ( int j = 0 ; j <= pTemp.second.first - iInputSize ; ++j )
        {
            if ( 0 == strInput.compare ( pTemp.second.second.substr ( j , iInputSize ) ) )
            {
                if ( pAnswer.second < pTemp.second.first )        // Longer music
                {
                    pAnswer.first = pTemp.first ;
                    pAnswer.second = pTemp.second.first ;
                }

                break ;
            }
        }
    }


    return ( "" != pAnswer.first ) ? pAnswer.first : "(None)" ;
}