[프로그래머스] 방금그곡

문제

출처

이해

입력

• 기억한 멜로디의 문자열 m
  • 배열 크기: [1, 1439]
  • 원소 범위: [C, C#, D, D#, E, F, F#, G, G#, A, A#, B]
  • 원소의 의미: 음정
• 방송된 곡의 정보를 담은 배열 musicinfos
  • 배열 크기: [0, 100]
  • 원소 범위: 문자열
  • 원소의 의미: <시작 시각>,<끝난 시각>,<제목>,<악보>
    • 시각: 24시간 HH:MM 형식
    • 제목
      • 배열 크기: [1, 64]
      • 원소 범위: , 기호를 제외한 기호
    • 악보
      • 기억한 멜로디 문자열과 동일 조건

출력

• 조건과 일치하는 음악 제목을 출력

규칙

1. 멜로디와 악보에 사용되는 음은 12개이다.
2. 음은 1분에 1개씩 재생된다.
3. 음악은 처음부터 재생되며, 재생시간이 음악길이보다 길면 처음부터 다시 재생한다.
4. 조건을 만족하는 음악이 여러 개라면 재생된 시간이 제일 긴 음악 제목을 반환한다.
5. 재생된 시간이 같으면 먼저 입력된 음악 제목을 반환한다.
6. 조건을 만족하는 음악이 없으면 (None)을 반환한다.
7. 음악이 00:00를 넘겨서까지 재생되는 일은 없다.

예시

입력
m: "ABCDEFG"
musicinfos: ["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]

출력
"HELLO"

접근

이 문제는 특별한 알고리즘이 필요하지 않은 구현 문제이다. 멜로디를 체크하는 부분을 KMP로 작성할 수도 있지만 곡이 100개, 악보 길이 1439로 최악의 경우 대략 700 * 700 * 100으로 4900만 정도 되므로 나이브하게 탐색해도 큰 무리없이 통과할 수 있다.

시각을 처리하기 위해 datetime 라이브러리를 사용하고, 음정의 파싱을 위해 정규표현식 라이브러리를 사용하였다.

구현

from datetime import datetime as dt
import re

def solution(m, musicinfos):
    S, E, TITLE, MELODY = 0, 1, 2, 3

    # 시간 파싱
    parse = lambda s: dt.strptime(s, "%H:%M")

    # 음정 파싱
    p = re.compile('[CDEFGAB]#?')
    heard = p.findall(m)
    
    # musicinfos의 원소인 문자열을 다루기 쉽게 쪼갠다.
    infos = [s.split(',') for s in musicinfos]

    # 재생 시간 체크
    play_time = [(parse(infos[i][E]) - parse(infos[i][S])).seconds // 60 for i in range(len(infos))]

    # 실제 재생된 멜로디
    play_history = []

    # 모든 재생된 노래를
    for song in range(len(infos)):
        melody = p.findall(infos[song][MELODY])
        now = 0
        play_history.append([])
        # 재생된 시간만큼 재생하고 기록함
        for i in range(play_time[song]):
            play_history[-1].append(melody[now])
            now = (now + 1) % len(melody)
    
    # 나이브하게 문자열 포함 여부 확인하는 함수
    def included(melody):
        for i in range(len(melody) - len(heard) + 1):
            cnt = 0
            for j in range(len(heard)):
                if melody[i + j] == heard[j]:
                    cnt += 1
                else:
                    break
            if cnt >= len(heard):
                return True
        return False

    # 규칙 4와 5를 만족하도록 정렬함
    play = list(zip(range(len(play_time)), play_time, play_history))
    play.sort(key=lambda x: (-x[1], x[0]))
    
    # 앞에서부터 탐색하면서 가장 먼저 만족하는 음악을 찾음.
    for i, time, melody in play:
        if included(melody):
            return infos[i][TITLE]
    return "(None)"