Programmers | Level 2 | 방금그곡

Sep 11, 2024

Published byJynn

999

Programmers | Level 2 | 방금그곡

Problems

📘 Src: Programmers
🗂️ Cat: String

󰧭 Description

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

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

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

 Constraints

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

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

󰦕 Examples

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

Solutions

󰘦 Code

Solution.java

import java.util.*;

class Solution {
    public String solution(String m, String[] musicinfos) {
        String music = "(None)";  // 최종 반환할 곡의 제목, 기본값은 "(None)"
        int longestDuration = Integer.MIN_VALUE;  // 가장 긴 재생 시간을 기록할 변수
        m = convert(m);  // 기억한 멜로디를 변환해 샤프가 붙은 음을 처리
        
        // 주어진 곡 정보를 하나씩 처리
        for (String musicinfo : musicinfos) {
            String[] info = musicinfo.split(",");  // 곡 정보를 콤마로 구분하여 분리
            int currentDuration = duration(info[0], info[1]);  // 시작과 끝 시간을 통해 재생 시간 계산
            String melody = convert(info[3]);  // 악보 정보에서 샤프가 붙은 음 변환
            int n = melody.length();
            
            // 재생 시간에 맞춰 전체 멜로디를 생성
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < currentDuration; i++) {
                sb.append(melody.charAt(i % n));  // 재생 시간이 길면 반복하여 멜로디 생성
            }
            
            // 기억한 멜로디가 전체 멜로디에 포함되어 있는지 확인
            if (sb.indexOf(m) == -1) continue;  // 포함되지 않으면 다음 곡으로 넘어감
            
            // 현재 곡의 재생 시간이 가장 긴지 확인하고, 업데이트
            if (longestDuration < currentDuration) {
                music = info[2];  // 곡의 제목을 업데이트
                longestDuration = currentDuration;  // 가장 긴 재생 시간 갱신
            }
        }
        
        return music;  // 가장 긴 재생 시간을 가진 곡의 제목 반환
    }
    
    // 샤프가 붙은 음을 고유한 문자로 변환하여 비교를 용이하게 만듦
    private String convert(String melody) {
        return melody
            .replaceAll("A#", "a")
            .replaceAll("B#", "b")
            .replaceAll("C#", "c")
            .replaceAll("D#", "d")
            .replaceAll("E#", "e")
            .replaceAll("F#", "f")
            .replaceAll("G#", "g");
    }
    
    // 재생 시간을 계산하는 함수 (시작 시간과 종료 시간의 차이)
    private int duration(String startTime, String endTime) {
        String[] start = startTime.split(":");
        int startInMins = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]);  // 시작 시간을 분 단위로 변환
        
        String[] end = endTime.split(":");
        int endInMins = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]);  // 종료 시간을 분 단위로 변환
        return endInMins - startInMins;  // 시작과 종료 시간의 차이를 반환
    }
}

 Approach

이 문제는 네오가 기억한 멜로디와 방송된 음악의 악보를 비교하는 과정에서, 악보의 반복 재생과 기억한 멜로디가 곡의 일부일 수 있다는 점을 고려해야 합니다. 음악 정보를 주어진 재생 시간에 맞춰 문자열로 변환하고, 그 변환된 문자열에서 패턴 매칭을 통해 멜로디를 찾아내는 문자열 처리 문제입니다. 이를 해결하기 위해서는 악보의 반복 재생을 처리하고, 기억한 멜로디가 포함되는지 확인하는 문자열 패턴 매칭을 효과적으로 구현해야 합니다.

 Warning
문제 설명에서 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 이렇게 12가지라고 명시되어 있지만, 테스트케이스 34에서 B#이 등장하는 것으로 보아 문제에 오류가 있는 것 같습니다. 따라서, B# 음에 대한 처리도 추가해야 합니다.

1. 문제 분석

방송된 여러 곡 중에서, 네오가 기억한 멜로디와 일치하는 곡을 찾아내는 문제입니다. 처음에는 단순히 멜로디를 하나씩 비교하면서 매치하면 되겠다고 생각했지만, 문제를 풀어가면서 몇 가지 복잡한 요소들이 있음을 알게 되었습니다. 특히, 곡의 재생 시간과 반복 재생되는 경우, 그리고 C#, D#과 같은 샤프(#)가 붙은 음의 처리 부분이 예상보다 까다로웠습니다.

샤프가 붙은 음을 일반 음과 구분하지 않으면, 유사한 음을 잘못 매칭하는 상황이 발생할 수 있습니다. 예를 들어, 찾고자 하는 멜로디가 ABC일 때, 음악에 ABC# 같은 멜로디가 포함되어 있다면, 단순한 문자열 매칭으로는 두 멜로디가 같은 것으로 인식될 수 있습니다. 하지만 C와 C#은 서로 다른 음이므로, 이를 구분하는 것이 중요합니다. 그래서 저는 샤프 음을 고유한 문자로 변환하여 일반 음과 명확히 구분하는 방식을 사용했습니다.

또한, 기억한 멜로디가 곡의 일부일 수 있고, 재생 시간이 길거나 짧을 때 곡이 반복 재생될 수 있습니다. 이러한 조건을 처리하는 동시에, 여러 곡이 일치할 경우 가장 긴 재생 시간을 가진 곡을 선택해야 하며, 재생 시간이 동일하면 입력된 순서에 따라 곡을 선택해야 합니다. 이런 조건들이 문제를 더욱 복잡하게 만듭니다.

결론적으로, 이 문제를 해결하기 위해서는 재생 시간 계산, 문자열 변환, 패턴 매칭을 모두 고려해야 합니다. 특히 샤프 음을 처리하고 반복 재생된 멜로디를 정확히 비교하는 것이 이 문제의 핵심입니다.

2. 접근 방식

이 문제에서 가장 중요한 포인트는 재생 시간과 샤프(#) 음 처리입니다. 따라서 문제를 해결하기 위해서는 다음과 같은 단계가 필요합니다.

재생 시간 계산: 먼저, 각 음악의 방송 시작 시간과 종료 시간을 통해 재생 시간을 계산해야 합니다. 이를 통해 주어진 곡이 몇 분 동안 재생되었는지 알 수 있으며, 재생 시간이 짧으면 그만큼만 비교하고, 재생 시간이 길면 곡이 반복 재생되는 상황을 처리할 수 있습니다.
멜로디 변환: 문제에서 주어지는 멜로디에는 #이 붙은 음이 포함되어 있는데, 이 음을 정확히 처리하지 않으면 잘못된 결과를 얻을 수 있습니다. C#, D#과 같은 샤프 음은 일반 음과 다르기 때문에, 이를 악보에서 사용되지 않는 문자로 변경하여 비교하는 것이 핵심입니다. 예를 들어, C#은 c로, D#은 d로 변환하여, 동일한 음이 아닌 것을 명확히 구분할 수 있도록 처리합니다.
전체 멜로디 생성: 각 음악의 재생 시간을 기준으로 악보를 반복하여 전체 멜로디를 생성합니다. 주어진 악보가 재생 시간보다 짧으면 그 악보를 반복해서 이어붙이는 방식으로 재생 시간만큼의 멜로디를 만들어냅니다. 이를 통해 원래 음악의 길이와 상관없이 정확히 재생된 전체 멜로디를 구성할 수 있습니다.
기억한 멜로디와 비교: 네오가 기억한 멜로디와 생성된 전체 멜로디를 비교하여, 일치하는지 여부를 확인합니다. 멜로디의 일부라도 일치하면 해당 곡이 후보가 되며, 이 과정에서 변환된 샤프 음 처리가 제대로 이루어졌는지 확인하는 것이 중요합니다.
결과 결정: 여러 곡이 조건을 만족할 경우, 가장 긴 재생 시간을 가진 곡을 선택합니다. 만약 재생 시간이 동일하다면, 입력된 순서를 기준으로 가장 먼저 방송된 곡을 반환합니다.

좋은 접근입니다. 단계를 세분화하여 코드를 논리적으로 나누는 것은 가독성과 이해도를 높이는 데 도움이 됩니다. 제안하신 분류를 바탕으로 제목과 설명을 더 적절하게 구성해보겠습니다.

3. 샤프 음 처리

문제에서 C#, D# 등 샤프가 붙은 음은 일반 음과 구분이 되어야 합니다. 이를 위해 샤프 음을 일반 음과 혼동하지 않도록, 별도의 문자로 변환하는 작업이 필요합니다. 이때 악보에 사용되지 않는 소문자로 변환하여, 이후 비교를 쉽게 할 수 있게 처리합니다.

Solution.java

private String convert(String melody) {
    return melody
        .replaceAll("A#", "a")
        .replaceAll("B#", "b")
        .replaceAll("C#", "c")
        .replaceAll("D#", "d")
        .replaceAll("E#", "e")
        .replaceAll("F#", "f")
        .replaceAll("G#", "g");
}

4. 재생 시간 계산

곡의 재생 시간을 계산하는 것은 네오가 기억한 멜로디와 일치하는 부분을 찾기 위한 중요한 과정입니다. 문제 조건에 따르면, 곡의 멜로디는 1분마다 한 음이 추가되므로, 시작 시간과 종료 시간을 기반으로 곡이 실제로 재생된 시간을 분 단위로 정확하게 계산해야 합니다.

이를 위해, 시간 정보를 HH:MM 형식에서 분 단위로 변환하여 처리합니다. 이 값은 이후 멜로디 생성에 사용됩니다.

Solution.java

private int duration(String startTime, String endTime) {
    String[] start = startTime.split(":");
    int startInMins = Integer.parseInt(start[0]) * 60 + Integer.parseInt(start[1]);  // 시작 시간을 분 단위로 변환
    
    String[] end = endTime.split(":");
    int endInMins = Integer.parseInt(end[0]) * 60 + Integer.parseInt(end[1]);  // 종료 시간을 분 단위로 변환
    
    return endInMins - startInMins;  // 재생 시간 계산
}

5. 재생 시간에 따른 전체 멜로디 생성

곡이 재생된 시간 동안의 전체 멜로디를 생성하는 단계입니다. 여기서 중요한 점은 주어진 악보의 길이보다 재생 시간이 길다면 악보는 반복 재생되고, 반대로 재생 시간이 짧다면 그만큼만 재생된다는 점입니다.

우선, 방송된 곡 정보를 순회하며 악보에서 샤프가 붙은 음들을 고유한 문자로 변환하고, 각 곡의 재생 시간을 계산합니다. 샤프 음은 C#을 c, D#을 d와 같은 고유 문자로 변환하여 일반 음과 구분하여 처리합니다.

재생 시간이 악보의 길이보다 긴 경우, 멜로디는 반복 재생됩니다. 이를 위해 인덱스를 악보의 길이로 나누어 순환시켜 멜로디를 반복 생성합니다. 예를 들어, ABC#D를 변환한 ABcd가 8분 동안 재생된다면 ABcdABcd처럼 반복되는 멜로디가 생성됩니다.

반대로 재생 시간이 악보 길이보다 짧다면, 악보의 처음부터 재생 시간만큼만 잘라서 사용합니다. 예를 들어, 변환된 멜로디가 ABcd이고 재생 시간이 3분이라면 ABc처럼 필요한 만큼만 사용됩니다.

이 과정을 통해 각 곡의 전체 멜로디를 생성하고, 네오가 기억한 멜로디와 비교할 수 있는 준비를 마칩니다.

Solution.java

for (String musicinfo : musicinfos) {
    String[] info = musicinfo.split(",");  // 음악 정보 분리
    int currentDuration = duration(info[0], info[1]);  // 재생 시간 계산
    String melody = convert(info[3]);  // 샤프 음 변환
    int n = melody.length();
    StringBuilder sb = new StringBuilder();
    
    // 재생 시간에 맞춰 전체 멜로디 생성 (반복되는 경우 처리)
    for (int i = 0; i < currentDuration; i++) {
        sb.append(melody.charAt(i % n));  // 악보를 순환하며 멜로디 생성
    }
    ...
}

6. 기억한 멜로디 비교 및 최장 재생 시간 갱신

생성된 전체 멜로디에서 네오가 기억한 멜로디가 포함되어 있는지 확인합니다. 기억한 멜로디와 전체 멜로디를 비교하여 일치하는 부분이 있는 경우, 해당 곡이 조건을 충족하게 됩니다.

만약 기억한 멜로디가 포함되어 있다면, 해당 곡의 재생 시간이 가장 긴지 확인하고, 이전에 저장된 곡보다 재생 시간이 길다면 해당 곡의 제목과 재생 시간을 갱신합니다. 재생 시간이 같은 경우에는 먼저 입력된 곡을 우선시하기 때문에 갱신하지 않고 현재 곡을 유지합니다.

Solution.java

for (String musicinfo : musicinfos) {
    ...
    // 이전 단계에서 전체 멜로디를 생성하고 변환한 네오의 기억한 멜로디와 비교
    if (sb.indexOf(m) == -1) continue;  // 기억한 멜로디가 전체 멜로디에 포함되어 있지 않다면 해당 곡을 무시
    
    // 재생 시간이 가장 긴 곡 선택
    if (longestDuration < currentDuration) {
        music = info[2];  // 현재 곡의 제목 저장
        longestDuration = currentDuration;  // 가장 긴 재생 시간 갱신
    }
}

7. 결과 반환

모든 루프가 종료된 후에는, 기억한 멜로디와 일치하는 곡들 중에서 가장 긴 재생 시간을 가진 곡의 제목이 저장되어 있을 것입니다. 만약 여러 곡이 동일한 재생 시간을 가졌다면, 입력된 순서에 따라 먼저 입력된 곡이 우선 저장되어 있을 것입니다. 마지막으로, 저장된 곡의 제목을 반환하여 최종 결과를 도출합니다.

// 최종적으로 가장 긴 재생 시간을 가진 곡의 제목을 반환
return music;

󰄉 Complexity

⏳ TC: O(n)
💾 SC: O(n)

곡의 수에 비례하여 처리되므로 시간 복잡도는 O(n)입니다. 각 곡에 대해 멜로디를 반복하여 재생 시간을 만들고, 네오가 기억한 멜로디와 비교하는 작업을 수행하기 때문에, 주된 시간 소요는 곡의 개수에 따라 결정됩니다. 곡의 재생 시간과 멜로디 길이가 영향을 미칠 수 있지만, 전체 프로세스는 곡의 수에 의존하므로 시간 복잡도는 O(n)으로 단순화할 수 있습니다. 또한, 곡 정보와 변환된 멜로디를 저장하는 데 필요한 공간을 사용하므로 공간 복잡도 역시 O(n)입니다.

Algorithm
String