[Python] Level 2. [3차] 방금그곡

프로그래머스

 

문제 설명

네오가 기억하는 멜로디와 일치하는 곡을 찾아낸다.

✅ 한 음악을 반복해서 재생할 때도 있어서 곡의 끝부분과 처음 부분이 이어진 멜로디를 기억할 수도 있다.

✅ 한 음악을 중간에 끊을 경우 원본 음악을 들은 거라도 네오가 기억한 멜로디와 다를 수 있다.

✅ 멜로디와 일치하는 곡이 여러 개라면 그 중 재생 시간이 가장 긴 음악을 답으로 구한다.

 

 

문제 풀이

알고리즘 유형

구현

 

풀이 설명

1. 재생 시간 구하기

멜로디와 일치하는 곡이 여러 개인 경우를 생각해야 하므로, 곡의 시작 시각과 끝난 시각 사이의 시간(분)을 구한다.

예를 들어, 곡의 시작 시각과 끝난 시각이 각각 12:00, 12:45라면 45분을 구하는 함수를 정의한다.

def calculatePlaytime(s, e):
    s_hour, s_minute = map(int, s.split(':'))
    e_hour, e_minute = map(int, e.split(':'))
    
    return (e_hour * 60 + e_minute) - (s_hour * 60 + s_minute)

✅ 파라미터 s, e는 hh:mm의 형태를 갖는 string 형식이다.

 

2. 악보에서 음 분리하기

음을 한 개씩 분리하여 하나의 배열에 담아 리턴하는 함수를 정의한다.

예를 들어 악보가 "ABC#AB"라면 ["A", "B", "C#", "A", "B"] 배열을 리턴한다.

def notesToArray(notes):
    arr = []
    idx = 0
    
    while idx < len(notes):
        if idx + 1 < len(notes) and notes[idx + 1] == '#':
            arr.append(notes[idx:idx+2])
            idx += 2
        else:
            arr.append(notes[idx])
            idx += 1
            
    return arr

 

3. 재생되는 악보에 네오가 기억하는 멜로디 찾기

def findall(target, notes):
    answer = []
    idx = 0
    
    while idx < len(notes):
        if notes[idx: idx + len(target)] == target:
            answer.append(idx)
            idx += len(target)
        else:
            idx += 1
            
        if idx + len(target) > len(notes):
            break
            
    return answer

✅ 파라미터 target은 네오가 기억하는 멜로디 string이고, notes는 재생되는 악보 string을 받는다.

✅ 재생되는 악보에 멜로디가 있다면 악보에서 멜로디가 시작하는 인덱스를 모두 구한다. 모두 구하는 이유는 예를 들어 target이 "ABC"이고 notes가 "ABC#ABC"라면 notes에서 target이 포함하는 인덱스는 0이 아닌 4여야 하기 때문이다. 

따라서 이런 경우를 방지하기 위해 모든 인덱스를 찾는다.

 

4. 재생되는 시간만큼 악보 길이 조절하기

우선 재생시간(playtime)을 앞서 정의한 calculatePlaytime 함수를 통해 구한다.

 

재생시간과 악보 길이를 비교해 악보 길이를 조절한다.

• 재생시간이 악보 길이보다 짧다면, 악보 길이를 재생시간만큼 줄인다.
• 재생시간이 악보 길이보다 길다면, 악보 길이를 재생시간 이상이 되도록 반복 재생한다.

musics = []
    
for mi in musicinfos:
    s, e, name, notes = mi.split(',')
    playtime = calculatePlaytime(s, e)
    notes = notesToArray(notes)
        
    # 재생 시간만큼 악보 길이 조절하기
    if playtime < len(notes):
        played_notes = ''.join(notes[:playtime])
    else:
        played_notes = ''.join(list(notes) * math.ceil(playtime / len(notes)))

 

5. 악보에 멜로디가 있는지 확인하기

for offset in findall(m, played_notes):
    if offset + len(m) <= len(played_notes):
        if offset + len(m) == len(played_notes) or played_notes[offset + len(m)] != '#':
            musics.append((playtime, name))

4번 과정에서 구한 악보를 통해, 해당 악보에 멜로디가 있다면 musics 리스트에 재생 시간과 해당 곡 이름을 튜플 형식으로 추가한다.

✅ 이 때 예를 들어 멜로디가 "ABC"이고 악보가 "ABC#"일 경우, 악보에 멜로디가 없으므로 악보에서 찾은 멜로디 끝에 '#'이 붙는지 확인하는 작업이 필요하다.

 

6. 답 구하기

모든 악보에 멜로디와 매치하는 곡이 없다면 "(None)"을 리턴하고, 

그렇지 않다면 재생 시간을 기준으로 musics를 내림차순 정렬하여 가장 긴 재생시간을 갖는 곡을 리턴한다.

if not musics:
    return "(None)"

musics.sort(key=lambda x: -x[0])
return musics[0][1]

 

 

풀이 코드

import math

# 재생 시간 구하는 함수
def calculatePlaytime(s, e):
    s_hour, s_minute = map(int, s.split(':'))
    e_hour, e_minute = map(int, e.split(':'))
    
    return (e_hour * 60 + e_minute) - (s_hour * 60 + s_minute)


# 악보에서 음을 분리하는 함수
def notesToArray(notes):
    arr = []
    idx = 0
    
    while idx < len(notes):
        if idx + 1 < len(notes) and notes[idx + 1] == '#':
            arr.append(notes[idx:idx+2])
            idx += 2
        else:
            arr.append(notes[idx])
            idx += 1
            
    return arr
     
 
# 악보에서 네오가 기억하는 음을 모두 찾는 함수
def findall(target, notes):
    answer = []
    
    idx = 0
    while idx < len(notes):
        if notes[idx: idx + len(target)] == target:
            answer.append(idx)
            idx += len(target)
        else:
            idx += 1
            
        if idx + len(target) > len(notes):
            break
            
    return answer
    

def solution(m, musicinfos):
    musics = []
    
    for mi in musicinfos:
        s, e, name, notes = mi.split(',')
        playtime = calculatePlaytime(s, e)
        notes = notesToArray(notes)
        
        if playtime < len(notes):
            played_notes = ''.join(notes[:playtime])
        else:
            played_notes = ''.join(list(notes) * math.ceil(playtime / len(notes)))

        for offset in findall(m, played_notes):
            if offset + len(m) <= len(played_notes):
                if offset + len(m) == len(played_notes) or played_notes[offset + len(m)] != '#':
                    musics.append((playtime, name))
        
    musics.sort(key=lambda x: -x[0])
    
    if not musics:
        return "(None)"
    return musics[0][1]