문제 보기 · Level 2 · 2018 KAKAO BLIND RECRUITMENT (3차) · 정답률 51% · 푼 사람 11,787명 (2026-09-30 기준)1
문제
라디오에서 나온 곡마다 시작·끝 시각, 제목, 악보가 주어진다. 음은 1분에 하나씩 재생된다. 재생 시간이 곡보다 길면 처음부터 반복하고, 짧으면 중간에서 끊긴다. 기억한 멜로디 m이 실제로 재생된 음열 안에 들어 있는 곡을 찾는다. 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개다. 해당 곡이 여럿이면 재생 시간이 가장 긴 곡을, 그것도 같으면 먼저 입력된 곡을 고른다. 제목을 돌려주고, 없으면 "(None)"을 돌려준다.
- m과 악보는 음 1~1,439개
- 곡 최대 100개
- 재생이 자정을 넘기지 않는다
풀이
막히면 한 단계씩 펼친다2.
필요한 개념
- 문자열 파싱과 정규 표현식: 두 글자짜리 음(C#)을 한 글자로 바꿔 “한 글자 = 한 음”으로 만들기
- 시간·날짜 계산: 재생 시간을 분으로 구하기
1단계 · 작은 예로 손으로 풀기
기억한 멜로디 “CD”, 곡 X는 12:00~12:03(3분), 악보 “DC”
- 3분 동안 D, C, D가 재생된다 → “DCD”
- “DCD” 안에 “CD”가 있다 → X가 답
함정 하나: 멜로디 “C”, 곡 Y의 악보 “C#”(1분). 글자 그대로 찾으면 “C#” 안에 “C”가 있어 맞는 것처럼 보인다. 하지만 C#은 C와 다른 음이다. 그래서 C#을 한 글자로 바꿔 둬야 한다.
2단계 · 가장 단순한 방법과 그 속도
곡마다 재생된 음열(최대 1,439음)을 만들고 그 안에서 멜로디를 찾는다. 곡이 100개라 문자열 찾기 100번이다. 넉넉하다. 어려움은 # 음, 반복·끊김, 같은 결과일 때 고르는 규칙이다.
3단계 · 핵심 아이디어
- 한 음을 한 글자로: C# → c, D# → d, F# → f, G# → g, A# → a처럼 바꾼다. 문제의 12음에는 없지만 B#도 b로 바꿔 두면 안전하다. 이제 문자열 길이 = 음 수다.
- 재생된 음열: 재생 시간 d분이면 악보를 충분히 반복한 뒤 앞에서 d글자만 자른다:
(악보 * (d // len(악보) + 1))[:d]. d를 악보 길이 L로 나눈 몫이 q, 나머지가 r이면 d = qL + r(0 ≤ r < L)이라, q + 1번 이어 붙인 길이 (q + 1)L은 늘 d보다 길다(나눗셈 정리). - 찾기:
m in 재생된음열. - 고르기: 맞는 곡 중 재생 시간이 더 긴 경우에만 답을 바꾼다. 같으면 바꾸지 않으니 먼저 나온 곡이 남는다.
4단계 · 코드 흐름
#음을 한 글자로 바꾸는 함수를 만들고, 멜로디 m에 적용한다.- 곡마다 쉼표로 네 조각(시작, 끝, 제목, 악보)을 나눈다.
- 재생 시간 = 끝(분) − 시작(분). 악보도 바꾸고 재생된 음열을 만든다.
- m이 들어 있고 재생 시간이 지금까지의 최고보다 길면 답을 바꾼다.
- 답(없으면 “(None)”)을 돌려준다.
5단계 · 파이썬 코드
def solution(m, musicinfos):
def norm(s): # 두 글자 음을 한 글자로
for a, b in (("C#", "c"), ("D#", "d"), ("F#", "f"),
("G#", "g"), ("A#", "a"), ("B#", "b")):
s = s.replace(a, b)
return s
def minutes(t):
h, mm = map(int, t.split(":"))
return h * 60 + mm
m = norm(m)
best, best_len = "(None)", 0
for info in musicinfos:
start, end, title, sheet = info.split(",")
dur = minutes(end) - minutes(start)
sheet = norm(sheet)
played = (sheet * (dur // len(sheet) + 1))[:dur]
if m in played and dur > best_len: # 같은 길이면 먼저 나온 곡이 남는다
best, best_len = title, dur
return best
sheet * k: 문자열을 k번 이어 붙인다.[:dur]: 앞에서 dur글자(= dur분)만 남긴다. 곡보다 짧으면 끊기고, 길면 반복된 만큼 들어간다.m in played: 이어진 부분 문자열로 들어 있는지 본다.
6단계 · 실행 추적
m = “CC#BCC#BCC#BCC#B” → 바꾸면 “CcBCcBCcBCcB”(12음)
| 곡 | 재생 시간 | 바꾼 악보 | 재생된 음열 | m이 있나 |
|---|---|---|---|---|
| FOO | 30분 | CcB | “CcB” × 10 (30음) | 예 |
| BAR | 8분 | CcBCcBCcB | 앞 8음 “CcBCcBCc” | 아니오 (12음보다 짧다) |
답은 “FOO”다.
7단계 · 복잡도와 흔한 실수
곡마다 재생 음열(최대 1,439음)을 한 번 만들고 그 안에서 멜로디를 찾는다. 찾기는 최악에 (멜로디 길이 × 음열 길이)번 비교지만, 곡이 100개뿐이라 금방 끝난다.
#을 처리하지 않아 “C”가 “C#”에 맞는다고 판단한다.- 재생 시간이 악보보다 짧을 때 자르지 않거나, 길 때 반복하지 않는다.
- 같은 재생 시간에서 나중 곡으로 바꾼다(
>=를 씀). - 결과가 없을 때
"(None)"대신None이나 빈 문자열을 돌려준다.