문제 출처
1. 문제설명
- 네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다.
- 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다.
- 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다.
- 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다.
- 가정을 통해 음악의 제목을 구하라!
- 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
- 네오가 기억한 멜로디와 악보에 사용되는 음은
C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
- 각 음은 1분에 1개씩 재생된다.
- 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다.
- 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
- 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
- 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다.
- 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
- 문제 분류
2. 알고리즘 설계
split, in 등 파이썬의 강력한 문자열 함수를 사용하면 아주 편할 거 같아 Python으로 구현하였다.- 정보가 문자열로 입력되어 컴마로 구분되어 있다.
- 시간 정보를 계산을 위해 분 단위로 환산하였다.
- 음악 재생 시간이 더 길거나 짧을 때를 대비하여 문자열을 복사해주었다.
- 마지막으로 sort 함수를 통해 정렬
재생된 시간이 제일 긴 음악 제목, 재생된 시간도 같을 경우 먼저 입력된 음악 제목
3. 전체 코드
def time_c(t):
return int(t.split(':')[0])*60 + int(t.split(':')[1])
def change(x):
exc = {'C#':'1','D#':'2', 'F#':'3', 'G#':'4', 'A#':'5'}
for k, v in exc.items():
x = x.replace(k, v)
return x
def solution(m, musicinfos):
answer = []
for info in musicinfos:
info = info.split(',')
info[3] = change(info[3])
T = time_c(info[1]) - time_c(info[0])
if T >= len(info[3]):
M = info[3] * (T//len(info[3])) + info[3][:T%len(info[3])]
else:
M = info[3][:T]
if change(m) in M:
answer.append([T, info[2]])
if len(answer) == 0:
return '(None)'
else:
return sorted(answer, key=lambda x: -x[0])[0][1]
4. 소감
- 알고리즘 주 언어는 C++이지만, 파이썬의 문자열 함수는 매우 강력한 거 같다.
- 파이썬이 지원된다면, 문자열 문제는 파이썬으로 풀이해서 시간을 아끼는 전략을 취해봐야 겠다.