방금 그곡(카카오) 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

노래 정보들이 주어지며 찾고자 하는 멜로디가 포함된 노래를 찾는 구현 문제이다. 문제에서 처리해야할 사항들을 정리하면 아래와 같다.

1. 주어지는 멜로디를 어떻게 처리할 것인가?
>> 멜로디에는 1글자로 되어 있는 'C','D' 등과 2글자로 되어 있는 '~#' 이 존재
>> 멜로디의 개수를 구해야하기 때문에, '#'이 들어간 멜로디는 소문자로 변경
>> eg. 'C#' -> 'c', 'D#' -> 'd'

2. 재생 시간을 통해 1에서 처리한 멜로디를 어떻게 사용할 것인가?
>> 노래를 반복할 수도 있고, 중간에 끊을 수도 있다
>> 스트리밍 시간을 구하고, 노래시간을 나눠서 몫, 나머지를 활용한다
>> 몫 = 노래 반복횟수 / 나머지 = 처음에서 중간까지
>> eg. 스트리밍 시간 = 18분, 노래시간 = 7분인 경우 > 몫=2, 나머지=4
>>     즉, 2번 반복하고 0~4분까지 재생 후 종료

 

시간 복잡도

musicinfo의 개수 만큼 for문을 순회하며, 내부에서 멜로디 문자열을 변환하는 과정에서도 for문이 수행된다. musicinfo의 최대개수는 100개, 멜로디의 문자열 개수는 1439개 이므로 시간 내에 동작한다.

 

 

코드

## 멜로디 '#'이 붙는 것들을 소문자로 변경한다
def transform(m): 
    size=len(m)
    ret=""
    for i in range(size):
        if i+2<=size and m[i:i+2]=="C#":
            ret+='c'
        elif i+2<=size and m[i:i+2]=="D#":
            ret+='d'
        elif i+2<=size and m[i:i+2]=="F#":
            ret+='f'
        elif i+2<=size and m[i:i+2]=="G#":
            ret+='g'
        elif i+2<=size and m[i:i+2]=="A#":
            ret+='a'
        elif m[i]!="#":
            ret+=m[i]
    return ret
                    
        
def solution(m, musicinfos):
    m=transform(m)
    answer = "(None)"
    max_v=0
    for music in musicinfos:
    
    	## 스트리밍할 시간을 구한다
        start,end,name,melody=music.split(",")
        end_h,end_m=map(int,end.split(":"))
        start_h,start_m=map(int,start.split(":"))
        gap=(end_h*60+end_m)-(start_h*60+start_m)
        
        #멜로디 철자를 변환 후 총 재생되는 멜로디를 구한다
        melody=transform(melody)
        melody_size=len(melody)
        repeat=gap//melody_size
        remain=gap%melody_size
        streaming=melody*repeat+melody[:remain]
        
        ## 찾고자 하는 멜로디가 존재하고 길이가 크다면 값을 갱신한다
        if m in streaming and len(streaming)>max_v:
            answer=name
            max_v=len(streaming)
        
    return answer