시간을 줄이는 섬세한 코딩기술

1. 문제

 

https://programmers.co.kr/learn/courses/30/lessons/17683

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

 

라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다.

 

그럴 때 네오는 다음 포털의 ‘방금그곡’ 서비스를 이용하곤 한다.

 

방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

 

네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다.

 

그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서

 

네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다.

 

반대로 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다.

 

그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다.

 

다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

 

1. 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.

 

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

 

3. 각 음은 1분에 1개씩 재생된다.

 

음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다.

 

음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생시간만큼만 재생된다.

 

4. 음악이 00:00을 넘겨서까지 재생되는 일은 없다.

 

5. 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다.

 

재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.

 

6. 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

 

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

 

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

 

 

2. 제한사항

 

m은 음 1개 이상 1439개 이하로 구성되어 있다.

 

musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ‘ , ‘로 구분된 문자열이다.

 

음악의 시작 시각과 끝난 시각은 24시간 HH:MM형식

 

음악 제목은 ‘ , ‘이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.

 

악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

 

 

3. 입출력예시

 

 

4. 나의 풀이

 

musicinfos에서 하나씩 돌아서 , 를 기준으로 split을 수행

 

answer_list = []

for music in musicinfos:
    
    music_info = music.split(',')

 

다음 음에 #이 포함된다는게 까다로울 수가 있다

 

python 문자열에서는 C#을 2개로 보는데 문제 조건은 C#도 1개로 봐야한다는 거임

 

그래서 #이 들어간 list를 만들고

 

이들을 그냥 하나의 문자로 바꿔줘

 

여기서는 #앞에 붙은 문자를 소문자로 바꿔서 대체해줬음

 

special_list = ['C#', 'D#', 'F#', 'G#','A#']


#special_list = ['C#', 'D#', 'F#', 'G#', ' A#'] #공백을 넣으면 당연히 안돼

answer_list = []

for music in musicinfos:
    
    music_info = music.split(',')
    
    for special in special_list:
        
        m = m.replace(special, special[0].lower())
        
        music_info[3] = music_info[3].replace(special, special[0].lower())

 

처음에 special list부분에 공백을 넣어버려서 알고리즘을 맞게해도 자꾸 통과를 못하더라…

 

오타도 잘 신경을 써야한다는거 기억해야겠고

 

이제 음악의 재생시간을 구해야하는데 music_info에 0번째는 start time, 1번째는 end time이 있다

 

근데 이제 단순히 end time - start time하면 안된다는거 당연할거고

 

시와 분으로 나눠서 구해야한단 말이지

 

end time[:2]는 시가 저장되어 있고 end time[3:]은 분이 저장되어 있다

 

그래서 end_time[:2] - start_time[:2]로 시차를 구하고

 

end_time[3:] - start_time[3:]로 분차를 구했는데 이러면 안돼

 

일단은 문자열이라서 문자열 빼기 해봤자 계산이 안됨

 

그래서 int(end_time[:2]) - int(start_time[:2])로 시차를 구하고

 

int(end_time[3:]) - int(start_time[3:])로 분차를 구함

 

근데 이렇게 해도 안되는게

 

일단은 예를 들어 12:50분부터 13:10분까지 재생된거라면 20분을 내놔야하는데

 

13-12로 1시간 차이 난다고 하고 10-50해서 -40분 차이 난다고 해버린단 말이지

 

그래서 문제 조건이 1분에 1개 재생된다고 했으므로 분차만 구하면 된다는 점에 주목해서

 

00:00을 기준으로 end time은 몇분이 흘렀는지

 

start time은 몇분이 흘렀는지 분으로 바꾼다음에

 

end time에서 start time빼주면 분차이를 구할 수 있다

 

end_time = int(music_info[1][:2])*60 + int(music_info[1][3:])

start_time = int(music_info[0][:2])*60 + int(music_info[0][3:])

play_time = end_time - start_time

 

다음으로 총 재생된 음악 길이를 구해야하는데

 

play_time을 기준으로 문제 조건에서 play_time보다 음악의 원래 길이가 더 길면 play_time만큼만 재생한다는 점

 

반대로 play_time이 음악의 원래 길이보다 더 길다면 play_time을 음악의 길이로 나눈 몫과 나머지를 이용해서

 

음악을 몫만큼 반복하고 나머지의 길이만큼 처음부터 slicing해서 붙여준다

 

if play_time < len(music_info[3]):
    
    melody = music_info[3][:play_time]
    
else:
    
    repeat_num , extra = divmod(play_time, len(music_info[3]))
    
    melody = music_info[3] * repeat_num + music_info[3][:extra]

 

 

divmod(a,b)를 이용하면 a/b의 몫과 나머지를 한번에 구할 수 있다

 

아무튼 이렇게 melody를 구한다음에 기억한 음 m이 melody안에 있으면 answer_list에 추가를 하고

 

if m in melody:
    
    if answer_list == []:
        
        answer_list.append((play_time, music_info[2]))
        
    else:
        
        if answer_list[0][0] >= play_time:
            
            continue
        
        else:
            
            answer_list.pop()
            answer_list.append((play_time, music_info[2]))
            
if answer_list == []:
    
    return '(None)'
    
else:
    
    return answer_list[0][1]

 

근데 중요한점이 문제 조건에서 조건에 맞는 음악이 여러개이면….

 

음악의 재생시간이 가장 긴 음악을 정답으로 내놓으라고 했단말이야

 

재생시간마저도 같다면 먼저 입력된 음악을 답으로 내놓으라 했단 말이지

 

그래서 answer_list == []이면 후보가 하나도 없으므로 play_time이랑 음악 제목을 추가해두고

 

만약에 answer_list에 후보가 있는데도 m이 melody에 있다면…

 

play_time을 서로 비교를 한다… play_time이 answer_list안에 들어간 음악이 더 길거나 같다면 continue로 그대로 진행시키고

 

반대로 새로 들어와야하는 후보의 play_time이 더 길다면 answer_list의 원소를 비우고 새 후보를 그대로 넣는다

 

for문을 다 돌고나서 answer_list가 []이면 (None)을 출력한다…

 

그렇지 않다면 후보가 있으니까 유일하게 들어간 후보의 제목을 그대로 return

 

여기서도 '(None)'인데 '(none)'이라해가지고… 통과 못할뻔 이런 섬세함 주의해야한다

 

 

5. 다른 풀이

 

비슷할것 같은데 가장 좋아요 많이 받은 풀이 살펴보면

 

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

 

내가 지적한대로 C#은 파이썬에서 2문자이지만 문제에서는 1문자로 인식하라했으므로 소문자로 대체해야하는데

 

for문을 안돌고 replace를 하나의 변수에 쭉 이어서 한줄로 전부 대체한 코딩

 

def solution(m, musicinfos):
    
    answer = [0,'(None)'] #time_len, title
    
    m = shap_to_lower(m)
    
    for info in musicinfos:
        
        split_info = info.split(',')

 

그 다음에 answer에 [(time_len), (title)]을 초기화하는데

 

먼저 조건이 일치하는 것이 없으면 출력하는 (None)으로 초기화

 

기억한 음 m의 # 들어간 문자를 소문자로 대체하고

 

나처럼 musicinfos에서 split해서 하나씩 검사를 해보는데

 

time_length = (int(split_info[1][:2])-int(split_info[0][:2]))*60+
              int(split_info[1][-2:])-int(split_info[0][-2:])
              
title = split_info[2]

part_notes = shap_to_lower(split_info[-1])

 

그 다음에 time_length랑 title, 음악 원래 음의 #도 소문자로 대체했는데

 

보면 시차에 60곱하고 분차를 구했는데… 이렇게 해도 되나보네???

 

근데 이게 내가 한 분으로 바꿔서 한거랑 결국 똑같은게

 

endtime = end_h*60+end_m

 

starttime = start_h*60+start_m으로 바꿨잖아

 

이걸 빼면 endtime-starttime = (end_h-start_h)*60+(end_m-start_m)으로 코딩이랑 똑같네… 신기방기

 

    full_notes = part_notes*(time_length//len(part_notes))+part_notes[:time_length%len(part_notes)]

    if m in full_notes and time_length>answer[0]:

        answer = [time_length,title]
    
return answer[-1]

 

 

다음은 나랑 똑같아… 음악의 총 재생 음을 구하는데 재밌는게 나처럼 if문을 안나눴네…

 

근데 안나눠도 되는게 음악 재생길이가 음보다 더 짧으면 몫이 0이 되어서 앞부분은 그냥 사라지고 뒷부분 문자열만 계산이 되거든…

 

그리고 최종적으로 만들어진 full note에 m이 존재하는지, 재생시간이 answer에 들어간것보다 더 긴지 검사해서 추가한 모습

 

근데 나처럼 if문으로 안나누고 깔끔하게 한번에 처리하는거 기억

 

 

6. 되돌아보기

 

문제를 결국 풀었다는게 확실히 실력이 늘었다는 방증이고

 

몇가지 섬세한 코딩이 좀 필요하다

 

6-1) C#, A#, G#등을 처리할때 소문자로 바꿔서 하나의 문자로 처리하게 만드는 기술

 

6-2) for문을 돌 수도 있지만 replace를 쭉 이어서 for문없이 한줄로 처리하는 다른 풀이의 기술

 

6-3) 시간 차이를 계산할때 00:00을 기준으로 끝 시간과 시작 시간을 분으로 바꿔서 분차를 구한 기술

 

datetime을 이용도 해봤는데 20배 더 느리더라(그래봤자 전체 2ms정도 걸리긴했는데) 그래서 권장하지 않는다

 

참고로 datetime에는 hours나 minutes가 없고 seconds만 있어서 seconds를 뽑은 다음에 minutes로 바꿔줘야함

 

6-4) 다음 divmode로 몫과 나머지를 한번에 구했다는점

 

6-5) 기타 문제 조건이나 오타같은거 세세하게 살펴봐야함

 

(None)이냐 (none)이냐… ‘A#’이냐 ‘ A#’이냐…

 

재생시간이 원래 음보다 더 짧을수도 있었다는 점…

 

원래 후보가 있다면 재생시간이 제일 긴 음악을 뽑아야하고, 재생시간도 같다면 먼저 입력된 것을 뽑아야하고

 

6-6) 그러기 위해서 stack/queue를 이용해서 넣었다가 뺐다를 이용했다는 점 기억하면 좋겠다

 

6-7) 다른 풀이랑 비교했을때 나는 if문으로 나누고 했는데 굳이 if문을 안써도 된다는 점이 인상적이어서 기억할 필요가 있다