[프로그래머스] Lv2. 방금그곡 (2018 카카오 공채)

🔗

풀이

KMP 알고리즘을 써야 풀리는 문자열 문제라고 생각했는데 그 정도 난이도는 아니다. 최대 길이가 2000을 넘지 않는다. 문제를 잘 읽어보면 풀리는 문자열 구현문제. 문제가 복잡한데 요약하면 아래와 같다.

A 문자열이 B 문자열 안에 있는가?

A 문자열은 m이고, B는 주어진 문자열에서 만들어내면 된다.

🅰️ 문자열 치환

음에는 C#, D# 같이 #이 붙는 경우가 있는데 이 경우에도 하나의 문자열로 치며 길이는 1이다. 그대로 두고 비교를 하면 ABC#라는 문자열 안에 ABC가 있는 것처럼 찾아질 수 있기 때문에 헷갈리지 않기 위해 모든 문자열은 1글자 문자열로 치환한다.

note = {'C#': '0', 'D#': '1', 'F#': '2', 'G#': '3', 'A#': '4', 'C': '5', 'D': '6', 'E': '7', 'F': '8', 'G': '9'}

def music_convert(s):
    for char in note:
        s = s.replace(char, note[char])
    return s

🎼 음악 정보 치환

우선 몇 분이 진행됐는지 시간 정보를 모두 분으로 치환해서 계산한다.

1분에 1개의 음이 나온다고 했기 때문에 재생시간(분)을 음악의 길이로 나눴을 때의 몫과 나머지로 전체 재생된 멜로디를 계산할 수 있다.

30분 재생됐고 음악의 길이가 3이라면 몫 = 10, 나머지 = 0으로 음악의 길이 * 10 + 음악의 길이[:나머지]가 전체 재생된 멜로디이다.

for i, info in enumerate(musicinfos):
    t1, t2, title, music = info.split(',')
    time = time_convert(t2) - time_convert(t1)
    music = music_convert(music)
    quo, r = divmod(time, len(music))
    melody = music * quo + music[:r]

🎧 조건에 일치하는 음악 찾기

찾으려는 음악 m은 반드시 재생된 멜로디여야 한다. 그 말은 만들어진 전체 재생 멜로디 안에 반드시 포함되어 있어야 한다. 여러 예외처리를 해도 되지만 in을 사용하면 된다.

또 문제에서는 조건에 일치하는 음악이 여러 개 있을 수 있다고 했다. 여러 개 중에서 재생 시간이 가장 긴 음악, 시간이 같다면 먼저 나온 음악을 출력하라고 했으므로 일치하는 음악의 정보를 담을 result 배열에 음악의 제목과 재생 시간 둘 다 저장한다.

만약 일치하는 음악이 없다면 '(None)'을 출력하라고 했으므로 음악 제목의 디폴트 값을 '(None)'으로 설정한다.

result = ["(None)", -1]
m = music_convert(m)
for i, info in enumerate(musicinfos):
    t1, t2, title, music = info.split(',')
    time = time_convert(t2) - time_convert(t1)
    music = music_convert(music)
    quo, r = divmod(time, len(music))
    melody = music * quo + music[:r]

    if m in melody and time > result[1]:
        result = [title, time]

return result[0]

⭕️ 전체 코드

def solution(m, musicinfos):
    note = {'C#': '0', 'D#': '1', 'F#': '2', 'G#': '3', 'A#': '4', 'C': '5', 'D': '6', 'E': '7', 'F': '8', 'G': '9'}

    def music_convert(s):
        for char in note:
            s = s.replace(char, note[char])
        return s

    def time_convert(t):
        h, m = map(int, t.split(':'))
        return h*60+m

    result = ["(None)", -1]
    m = music_convert(m)
    for i, info in enumerate(musicinfos):
        t1, t2, title, music = info.split(',')
        time = time_convert(t2) - time_convert(t1)
        music = music_convert(music)
        quo, r = divmod(time, len(music))
        melody = music * quo + music[:r]

        if m in melody and time > result[1]:
            result = [title, time]

    return result[0]
import heapq