[프로그래머스/Level2] 방금 그곡 (2018 카카오 블라인드)

문제 설명

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금 그 곡' 서비스를 이용하곤 한다. 방금 그 곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

 

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

 

• 방금 그 곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
• 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
• 음악이 00:00을 넘겨서까지 재생되는 일은 없다.
• 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
• 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

 

입력 형식

입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.

 

• m은 음 1개 이상 1439개 이하로 구성되어 있다.
• musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
  • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
  • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
  • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

 

출력 형식

조건과 일치하는 음악 제목을 출력한다.

 

입출력 예시

m	musicinfos	answer
"ABCDEFG"	["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"HELLO"
"CC#BCC#BCC#BCC#B"	["03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"]	"FOO"
"ABC"	["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]	"WORLD"

 

설명

첫 번째 예시에서 HELLO는 길이가 7분이지만 12:00부터 12:14까지 재생되었으므로 실제로 CDEFGABCDEFGAB로 재생되었고, 이 중에 기억한 멜로디인 ABCDEFG가 들어있다.
세 번째 예시에서 HELLO는 C#DEFGABC#DEFGAB로, WORLD는 ABCDE로 재생되었다. HELLO 안에 있는 ABC#은 기억한 멜로디인 ABC와 일치하지 않고, WORLD 안에 있는 ABC가 기억한 멜로디와 일치한다.

---

나의 풀이

[Python(파이썬)]

def sharp_check(melody): # '#'정리 하기
    m_temp = []
    if '#' in melody:
        for k in range(len(melody)):
            if melody[k] == '#':
                m_temp[-1] += '#'
            else:
                m_temp.append(melody[k])
        return m_temp
    else:
        return list(melody)

def solution(m, musicinfos):
    info, play_time, include_m_idx, include_m_time = [], [], [], []
    m = sharp_check(m)  # 기억하는 멜로디 # 정리

    for i in range(len(musicinfos)):
        time = []
        musicinfos[i] = (musicinfos[i].split(','))  # 음악 정보 문자열을 ',' 기준으로 잘라 리스트로 만들기
        # 음악 재생시간 구하기
        time.append(musicinfos[i][0].split(':'))
        time.append(musicinfos[i][1].split(':'))
        play_time.append((int(time[1][0])*60+int(time[1][1])) - (int(time[0][0])*60+int(time[0][1])))
        # info 음악의 # 정리
        m_temp = sharp_check(musicinfos[i][3])

        a, b = divmod(play_time[i], len(m_temp))
        info.append(m_temp * a + m_temp[:b])    # 재생시간만큼의 멜로디
    # 기억하는 멜로디의 음악 제목 찾기
    for j in range(len(info)):
        for l in range(len(info[j])):
            if info[j][l] == m[0]:
                idx = 0
                for check in range(len(m)):
                    if l+idx < len(info[j]) and m[check] == info[j][l+idx]:
                        if check == len(m)-1:
                            include_m_idx.append(j)
                        idx += 1
                    else:
                        break
    if len(include_m_idx) == 1: # 멜로디를 포함하는 음악이 1개
        return musicinfos[include_m_idx[0]][2]
    elif not include_m_idx: # 멜로디를 포함하는 음악이 X
        return '(None)'
    else:   # 멜로디를 포함하는 음악이 여러개
        for i in include_m_idx:
            include_m_time.append(play_time[i])
        return musicinfos[include_m_idx[include_m_time.index(max(include_m_time))]][2]

---

 

학습한 내용

풀이 과정
1. #이 포함된 음악 정리
2. musicinfos의 노래 정리하기
2-1. 음악 재생 시간 구하기
2-2. 악보 정보를 재생 시간 길이만큼 만들기(# 생각하기)
3. 기억한 멜로디의 음악 찾기
4. 조건이 일치하는 음악이 여러 개일 때

 

1. #이 포함된 음악 정리

 

예제 3번에서

"ABC"

["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]

첫번째 음악 C#DEFGABC#DEFGAB, 두번째 음악 ABCDE 일때 'ABC'를 찾으면 #을 분리해주지 않았을 때 

C#DEFGABC#DEFGAB에서 A, B, C#인데 A, B, C,#라고 생각하면 ABC가 포함되어 있다고 계산되어 답이 HELLO로 나올 수 있다. 

따라서 C#을 하나의 음처럼 생각할 수 있도록 구현해야 한다.

 

def sharp_check(melody): # '#'정리 하기
    m_temp = []
    if '#' in melody:
        for k in range(len(melody)):
            if melody[k] == '#':
                m_temp[-1] += '#'
            else:
                m_temp.append(melody[k])
        return m_temp
    else:
        return list(melody)

 

1) 멜로디에 '#'이 포함되어 있는지 검사 -> 있다면 2번으로 없다면 바로 list로 변환하여 반환
2) for문을 이용해 melody[k] == '#' 인지 check
2-1) '#'이라면 m_temp[-1]에 '#' 더해주기 ex) B, C, #, D 을 B, C#, D로
2-2) '#'이 아니라면 m_temp에 음을 append

 

#을 제거하는 다른 사람 방식

def convert_sharp(music):
    music = music.replace('C#', 'c')
    music = music.replace('D#', 'd')
    music = music.replace('F#', 'f')
    music = music.replace('G#', 'g')
    music = music.replace('A#', 'a')
    return music

 

• 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.

위처럼 12개라고 정해져 있기 때문에 #이 포함된 음들을 소문자로 대체해서 사용하면 for문을 사용하지 않고 더 간단히 구현할 수 있다는 걸 알았다.

 

 

 

2. musicinfos의 노래 정리하기

 

먼저 음악 정보 문자열을 ',' 기준으로 잘라 리스트로 만든다. 

musicinfos[i] = (musicinfos[i].split(','))

ex) "12:00,12:14, HELLO, C#DEFGAB" -> ['12:00', '12:14', 'HELLO', 'C#DEFGAB']

 

2-1. 음악 재생 시간 구하기

# 음악 재생시간 구하기
time.append(musicinfos[i][0].split(':'))
time.append(musicinfos[i][1].split(':'))
play_time.append((int(time[1][0])*60+int(time[1][1])) - (int(time[0][0])*60+int(time[0][1])))

ex) 12:00,12:14 -> [[12, 00], [12, 14]] -> 12 * 60 + 14 - 12 * 60 - 0 -> 14

 

2-2. 악보 정보를 재생 시간 길이만큼 만들기(# 생각하기)

 

문제에서 주어진 내용

각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.

 

m_temp = sharp_check(musicinfos[i][3])	# 1. #이 포함된 음악 정리 함수 호출

a, b = divmod(play_time[i], len(m_temp))
info.append(m_temp * a + m_temp[:b])    # 재생시간만큼의 멜로디

 

ex) ["12:00,12:14, HELLO, C#DEFGAB", "13:00,13:05, WORLD, ABCDEF"]

• "12:00,12:14, HELLO, C#DEFGAB" -> 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생

1) C#DEFGAB ('#' 정리 함수 sharp_check 호출) -> ['C#', 'D', 'E', 'F', 'G', 'A', 'B']

2) 14초와 len(m_temp)를 이용해 몫 나머지 구하기 -> divmod(14, 7) -> (2, 0)

3) m_temp * 2 + m_temp[ : 0] -> ['C#', 'D', 'E', 'F', 'G', 'A', 'B', 'C#', 'D', 'E', 'F', 'G', 'A', 'B']

 

•  "13:00,13:05, WORLD, ABCDEF" -> 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생

1)  ABCDEF(sharp_check 함수 호출) ->  ['A', 'B', 'C' , 'D', 'E', 'F']

2) 5초와 len(m_temp)를 이용해 몫 나머지 구하기 -> divmod(5, 6) -> (0, 5)

3) m_temp * 0+ m_temp[ : 5] -> ['A', 'B', 'C' , 'D', 'E']

 

 

 

3. 기억한 멜로디의 음악 찾기

 

# 기억하는 멜로디의 음악 제목 찾기
    for j in range(len(info)):
        for l in range(len(info[j])):
            if info[j][l] == m[0]:
                idx = 0
                for check in range(len(m)):
                    if l+idx < len(info[j]) and m[check] == info[j][l+idx]:
                        if check == len(m)-1:
                            include_m_idx.append(j)
                        idx += 1
                    else:
                        break

 

 

4. 조건이 일치하는 음악이 여러 개일 때

 

 if len(include_m_idx) == 1: # 멜로디를 포함하는 음악이 1개
        return musicinfos[include_m_idx[0]][2]	# 해당 음악 return
 elif not include_m_idx: # 멜로디를 포함하는 음악이 X
        return '(None)'
 else:   # 멜로디를 포함하는 음악이 여러개
        for i in include_m_idx:
            include_m_time.append(play_time[i])
        return musicinfos[include_m_idx[include_m_time.index(max(include_m_time))]][2]
        # 음악 재생시간이 가장 긴 음악 return

 

 

 

---

문제 출처

코딩테스트 연습 - [3차] 방금그곡

카카오 신입 공채 3차 코딩 테스트 문제 해설