항해99 TIL [12/8]

오늘은 알고리즘 시험을 보았다. 예상은 했지만 나에게는 쉽지 않은 문제였기에 제한 시간 동안 나름 씨름을 해 보았지만, 결국 완전하게 해결을 하지는 못했다. 하지만 이 알고리즘 주차 기간 동안 조금이라도 더 알고리즘을 이해할 수 있다면 그것만으로 큰 수확이라고 생각하고 여기에 시험 문제를 정리해보고자 한다.

[3차] 방금그곡

문제에서 구하는 것

▶ 자신이 들은 멜로디가 포함되어 있는 음악 중 재생된 시간이 제일 긴 음악 제목

따라서, 그러면 자신이 들은 멜로디가 각 음악에 포함되어 있는지 아닌지를 먼저 파악함. 그 뒤 포함되어 있는 음악들 중에서 재생된 시간이 가장 긴 음악의 제목을 반환하면 됨.

주의할 점

▶ 입출력 예시에서 HELLO는 C#DEFGABC#DEFGAB로, WORLD는 ABCDE로 재생됨. HELLO 안에 있는 ABC#은 기억한 멜로디인 ABC와 일치하지 않고, WORLD 안에 있는 ABC가 기억한 멜로디와 일치함. → ABC# 은 ABC 를 포함하지 않음. 즉, C# 과 C는 아예 다른 음이라는 것! 따라서 C# 과 C를 구분하기 위한 방법을 구해야 함.

✅ 첫 번째 방법: 문자열을 기준으로 묶어버리는 것.

C#DEFGABC#DEFGAB 라는 문자열을 ["C#", "D", E", "F", "G", "A", "B", "C#", "D", E", "F", "G", "A", "B"] 라고 하는 것. 그러면 이 안에 ABC 가 있는지 확인하기 위해서 배열을 순회하면서 "A", "B", "C" 원소가 순서대로 있는지 파악하면 됨.

✅ 두 번째 방법: #이 붙은 문자들을 치환해버리는 것.

C# → c, D# → d 처럼 둘 때,C#DEFGABC#DEFGAB 라는 문자열이 cDEFGABcDEFGAB 라고 표시가 됨. 그러면 이 안에 ABC 가 있는지 확인하기 위해 문자열을 돌면서 "ABC" 라는 부분 문자열이 있는지 파악하면 됨.


▶두 가지 경우 다 비슷한 시간 복잡도와 구현 난이도가 있지만, 두 번째 방법이 보다 편한 방법이라고 할 수 있기에 두 번째 방법 채택. python 에서는 문자열 찾기 관련된 함수가 많기 때문에 쉬울 수 있음.

우선 #이 붙은 문자들을 치환해버리기로 했으니, replace_step 이라는 함수를 만들어서 m의 #붙은 문자열들을 치환해주도록 함.

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


def solution(m, musicinfos):
    answer = ''
    m = replace_step(m)

    return answer

이제 musicinfos 를 순회하면서, music info 에서 원하는 정보를 뽑아보면 시작 시간, 끝나는 시간, 이름, 멜로디가 "," 라는 문자를 기준으로 이루어져있는데 이를 분리해서 변수에 담아봄. 음악의 시작 시각과 끝난 시각을 이용하는 용도는 단순히 이 음악이 몇초나 재생되었는지 밖에 없음. 따라서 end_time 에서 start_time 을 빼서 얼마나 재생되었는지, play_time 을 계산해봄.

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


def solution(m, musicinfos):
    answer = ''
    m = replace_step(m)

    for musicinfo in musicinfos:
        start_time, end_time, name, melody = musicinfo.split(",")
        play_time = (int(end_time[:2]) * 60 + int(end_time[3:])) - (int(start_time[:2]) * 60 + int(start_time[3:]))
        
    return answer

여기서, melody 에는 아직 C# 등의 문자가 남아있을테니 마찬가지로 치환을 해 주면, melody 및 그 멜로디가 몇초나 진행되었는지도 알 수 있음. 예를 들어, ABC라는 멜로디가 15초 진행되었다고 하면 ABCABCABCABCABC는 이렇게 계속 반복이 되었을 것이며 이는 3이라는 멜로디의 길이를 15초 동안 실행해주기 위해서 5번이 반복된 것. 만약 실행기간이 16초 였다면 ABCABCABCABCABCA 까지 실행되었을 것임.

즉, 멜로디의 모습과 실행시간을 이용해서 실제 실행된 멜로디를 알아와야 하는데 이를 구하기 위해 올림(실행시간 / 멜로디의 길이)을 통해서 멜로디를 반복할 숫자를 구하면 ABCABCABCABCABCABC 라는 문자열이 됨. 그리고 멜로디의 길이 까지 잘라주는데, 이 때 16까지 길이를 잘라주면 ABCABCABCABCABCA 가 되기 때문에, 실제 실행된 멜로디를 구할 수 있음.

import math


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


def solution(m, musicinfos):
    answer = ''
    m = replace_step(m)

    for musicinfo in musicinfos:
        start_time, end_time, name, melody = musicinfo.split(",")
        play_time = (int(end_time[:2]) * 60 + int(end_time[3:])) - (int(start_time[:2]) * 60 + int(start_time[3:]))

        melody = replace_step(melody)
        melody_repeated_count = math.ceil(play_time / len(melody))
        melody_played = (melody * melody_repeated_count)[:play_time]
    return answer

따라서 melody_played 는 ABCABCABCABCABCABC 가 만들어짐. 이 안에 m 이라는 문자열이 존재하는지 확인하는데 이 때, in 이라는 연산자를 쓰면 간단하게 구현가능.

최종적으로 구하려는 것은 자신이 들은 멜로디가 포함되어 있는 음악 중 재생된 시간이 제일 긴 음악 제목. 즉, 가장 재생된 시간이 긴 제목을 저장하고 있어야 함. 따라서 이를 구분하기 위해 max_play_time 이라는 변수를 만들고, answer 의 기본값을 None 으로 만듬. 만약 play_time 이 max_play_time 보다 크다면 answer 와 max_play_time 을 갱신하도록 함.

import math


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


def solution(m, musicinfos):
    answer = None
    max_play_time = 0
    m = replace_step(m)

    for musicinfo in musicinfos:
        start_time, end_time, name, melody = musicinfo.split(",")
        play_time = (int(end_time[:2]) * 60 + int(end_time[3:])) - (int(start_time[:2]) * 60 + int(start_time[3:]))

        melody = replace_step(melody)
        melody_repeated_count = math.ceil(play_time / len(melody))
        melody_played = (melody * melody_repeated_count)[:play_time]
        if m in melody_played and play_time > max_play_time:
            answer = name
            max_play_time = play_time

    return answer

그리고 '조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.' 라는 요구사항에 맞춰서 간단한 if 문도 추가하면 완료.

import math


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


def solution(m, musicinfos):
    answer = None
    max_play_time = 0
    m = replace_step(m)

    for musicinfo in musicinfos:
        start_time, end_time, name, melody = musicinfo.split(",")
        play_time = (int(end_time[:2]) * 60 + int(end_time[3:])) - (int(start_time[:2]) * 60 + int(start_time[3:]))

        melody = replace_step(melody)
        melody_repeated_count = math.ceil(play_time / len(melody))
        melody_played = (melody * melody_repeated_count)[:play_time]
        if m in melody_played and play_time > max_play_time:
            answer = name
            max_play_time = play_time
    if not answer:
        return "(None)"
    return answer