문제 접근

• 각 노래들이 라디오에서 얼마나 방송됐는지 시간을 정수로 변환한다.
• 네오가 들었던 멜로디를 #을 고려해서 한 음별로 끊어 읽은 리스트를 구한다.
• 각 노래들을 #을 고려해서 한 음별로 끊어 읽은 리스트를 구한다.
• 노래의 시작 음과 같은 음을 노래 음에서 찾으면, 그 음부터 시작해서 모듈로 연산을 통해, 네오가 들었던 멜로디가 끝날때까지 같은지 비교한다.
• 같은걸 찾았다면, true를 반환. 아니라면 false를 반환.

이 과정을 완전 브루트 포스가 아니라, LCS 알고리즘을 적용해서도 구할 수는 있을 것 같다. 하지만 이 문제에서 멜로디는 약 1400이기 때문에 브루트포스로 구해도 답을 찾을 수 있다.

문제 풀이

import java.util.*;

class Solution {
    public String solution(String m, String[] musicinfos) {
        ArrayList<String> pattern = convertToList(m);
        
        String answer = "(None)";
        int playTime = 0;
        StringTokenizer st;
        StringTokenizer timeSt;    
        for(int i=0; i<musicinfos.length; i++) {
            st = new StringTokenizer(musicinfos[i], ",");
            
            timeSt = new StringTokenizer(st.nextToken(), ":");
            int startH = Integer.parseInt(timeSt.nextToken());
            int startM = Integer.parseInt(timeSt.nextToken());
            
            timeSt = new StringTokenizer(st.nextToken(), ":");
            int endH = Integer.parseInt(timeSt.nextToken());
            int endM = Integer.parseInt(timeSt.nextToken());
            
            String name = st.nextToken();
            ArrayList<String> melody = convertToList(st.nextToken());

            int t = (startH == endH) ? endM - startM : (60-startM + (endH-startH-1)*60 + endM);
            
            boolean contains = isContains(pattern, melody, t);    
            if (contains && playTime < t) {
                answer = name;
                playTime = t;
            }
        }
        return answer;
    }
    
    ArrayList<String> convertToList(String m) {
        ArrayList<String> pattern = new ArrayList();
        for(int i=0; i<m.length()-1; i++) {
            if (m.charAt(i+1) == '#') {
                pattern.add(m.substring(i, i+2));
                i++;
            } else {
                pattern.add(m.substring(i, i+1));
            }
        }
        if (m.charAt(m.length()-1) != '#') {
            pattern.add(m.substring(m.length()-1, m.length()));
        }
        return pattern;
    }
    
    boolean isContains(ArrayList<String> pattern, ArrayList<String> melody, int t) {
        for(int s=0; s<melody.size() && s<t; s++) {
            if (melody.get(s).equals(pattern.get(0)) && s+pattern.size() <= t) {
                boolean contains = true;
                for(int j=0; j<pattern.size(); j++) {
                    if (!(melody.get((s+j)%melody.size()).equals(pattern.get(j)))) {
                        contains = false;
                        break;
                    }
                }
                
                if (contains) {
                    return true;
                }
            }
        }
        
        return false;
    }
 }