[코딩테스트][프로그래머스] 방금그곡

문제

https://school.programmers.co.kr/learn/courses/30/lessons/17683?language=python3

python

from collections import deque

def solution(m, musicinfos):
    answer = ''
    answer_list=[]
    num=0
    for music in musicinfos:
        num+=1
        start_t,end_t,title,melody=map(str,music.split(","))
        play_time=(int(end_t[0:2])-int(start_t[0:2]))*60+(int(end_t[3:5])-int(start_t[3:5]))
        q=deque(list(melody))
        melody_list=[]
        index=0
        while(q):
            now=q.popleft()
            if now!='#':
                melody_list.append(now)
                index+=1
            else:
                melody_list[index-1]+=now
        mq=deque(list(m))
        index_m=0
        m_list=[]
        while(mq):
            now=mq.popleft()
            if now!='#':
                m_list.append(now)
                index_m+=1
            else:
                m_list[index_m-1]+=now
                
        realtime_melody=[]
        for i in range(play_time):
            realtime_melody.append(melody_list[i%len(melody_list)])
        for i in range(len(realtime_melody)):
            include_tf=True
            for j in range(len(m_list)):
                if i+j>=len(realtime_melody) or realtime_melody[i+j]!=m_list[j]:
                    include_tf=False
                    break
            if include_tf:
                answer_list.append((play_time,num,title))
                break
    if len(answer_list)==0:
        answer="(None)"
        return answer
    answer_list.sort(key=lambda x:(-x[0],x[1]))
    answer=answer_list[0][2]
    
    return answer

java

import java.util.*;

class Solution {
    public String solution(String m, String[] musicinfos) {
        String answer = "";
        int longest_play_time=0;
        
        // m(기억한 멜로디) 분할
        String[] m_split=m.split("");
        ArrayList<StringBuilder> m_list=new ArrayList<>();
        Queue<String> mq=new LinkedList<>();
        for(String s:m_split){
            mq.offer(s);
        }
        int index_m=0;
        while(!mq.isEmpty()){
            String s=mq.poll();
            if(!s.equals("#")){
                m_list.add(new StringBuilder(s));
                index_m+=1;
            }else{
                m_list.get(index_m-1).append(s);
            }
        }
        for(int i=0;i<musicinfos.length;i++){
            String[] arr=musicinfos[i].split(",");
            int hour_diff=Integer.parseInt(arr[1].substring(0,2))-Integer.parseInt(arr[0].substring(0,2));
            int minute_diff=Integer.parseInt(arr[1].substring(3,5))-Integer.parseInt(arr[0].substring(3,5));
            int play_time=hour_diff*60+minute_diff;
            String title=arr[2];
            
            String[] melody_split=arr[3].split("");
            // 이게 노래가 분할된거
            ArrayList<StringBuilder> melody_list=new ArrayList<>();
            Queue<String> q=new LinkedList<>();
            for(String s:melody_split){
                q.offer(s);
            }
            int index_melody=0;
            while(!q.isEmpty()){
                String s=q.poll();
                if(!s.equals("#")){
                    melody_list.add(new StringBuilder(s));
                    index_melody+=1;
                }else{
                    melody_list.get(index_melody-1).append(s);
                }
            }
            ArrayList<StringBuilder> total_melody=new ArrayList<>();
            for(int t=0;t<play_time;t++){
                total_melody.add(melody_list.get(t%melody_list.size()));
            }
            for(int start=0;start<total_melody.size();start++){
                boolean tf=true;
                for(int st=0;st<m_list.size();st++){
                    if(start+st>=total_melody.size() || !total_melody.get(st+start).toString().equals(m_list.get(st).toString()))                     {
                        tf=false;
                        break;
                    }
                }
                if(tf){
                    if(longest_play_time<play_time){
                        longest_play_time=play_time;
                        answer=title;
                    }
                    break;
                }
            }
        }
        if(answer.equals("")){
            answer="(None)";
        }
        
        return answer;
    }
}

내 생각

• python 풀이시간 : 35분
• java 풀이시간 : 50분
• '#'을 포함하는 음들이 있기 때문에 이것을 파악하기 위해 전체 멜로디와 입력된 멜로디의 문자열을 하나씩 끊은 후 모든 문자열을 큐에 넣었다가 순서대로 빼면서 '#'이 출력된다면 전 계이름에 붙이는 작업을 수행한다. 이를 통해 #이 포함된 계이름이 구분이 된다.
• 곡의 플레이시간동안 진행되는 전체 흘러나오는 계이름들의 리스트가 있어야 사용자가 들은 멜로디와 비교해볼 수 있기 때문에 플레이시간을 반복문의 조건으로 하여 각 노래가 흘러나온 전체의 흐름을 저장한다. 그 후 이중 반복문을 통해서 사용자가들은 멜로디와 전체 흐름의 멜로디를 비교하여 포함여부를 확인하고 포함되었다면 가장 플레이타임이 긴 것인지의 유무를 가지고 정답에 넣는다. 없다면 None을 출력한다.
• 비교과정에서 전체 흐름의 멜로디를 넘어서거나 해당 for문의 시작점에서 부터 시작한 비교에서 하나라도 틀린다면 다른 시작점에서 찾아야하기 때문에 break로 for문을 이탈한다.