프로그래머스 - [3차] 방금 그곡

[3차] 방금 그곡 : https://programmers.co.kr/learn/courses/30/lessons/17683#

Problems

---

Solves

네오가 들은 멜로디 m이 musicinfos에 있는 악보에 포함되어있는지 확인 한다.
musicinfos를 순차적으로 확인 한 후 m이 포함된 멜로디가 있는 음악 제목을 반환하는 문제이다.
이 때 멜로디가 포함된 음악이 여러개라면 음악 재생 시간이 가장 긴 음악을, 재생 시간이 동일 할 경우 가장 먼저 저장된 음악 제목을 반환한다. 그리고 멜로디가 포함된 음악이 없다면 (None)을 반환한다.

먼저 각 음악 정보의 악보에 m 멜로디가 포함되어있는지 확인해야한다.
m 멜로디와 해당 음악 정보를 setMelody()를 통해 1차 배열화하고 음악 정보의 index를 [m의 index]%[음악 정보 길이]로 하나하나 비교해가며 포함여부를 확인한다.
만약 포함되어있다면 isFind를 true로 갱신한다. 이때 더 이상의 탐색을 필요 없으므로 isFind여부를 통해 해당 음악의 악보의 탐색을 중단하고 해당 음악 정보를 PQ에 저장해준다.

그 다음 저장된 음악 정보가 있다면 음악 정보가 담긴 PQ에서 가장 앞에있는 음악 제목을 반환한다.
(PQ의 정렬 기준을 음악 정보의 재생 시간 내림차순)
정보가 없다면 초기화된 (None)이 반환된다.

---

Code

import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Collections;
class Solution {
    public String solution(String m, String[] musicinfos) {
        String answer = "(None)";
        
        //m의 배열화
        String[] M = setMelody(m);
        //m이 포함된 음악 정보를 저장할 PQ
        PriorityQueue<Music> musicPQ = new PriorityQueue<>();
        
        //음악 정보 순차 탐색
        for(String musicinfo : musicinfos){
            String[] info = musicinfo.split(",");
            //재생 시간 변환
            int runTime = runTime(info[0],info[1]);
            String title = info[2];
            //해당 음악의 멜로디 배열화
            String[] melody = setMelody(info[3]);
            //해당 음악의 멜로디에 m의 포함여부
            boolean isFind = false;
            //해당 음악의 실행시간 만큼 탐색
            for(int i=0;i<runTime;i++){
                int j = i;
                //음악의 악보 시작점부터 m과 하나하나 비교
                for(int l=0;l<M.length;l++){
                	//악보의 길이가 m보다 작고 재생시간이 악보보다 길다면 m은 악보가 이어진 값일수도 있기 때문에 악보의 시작점(i)부터 m의 길이 까지 비교를 해야한다. 
                    if(M[l].equals(melody[j%melody.length])){
                        isFind = true;
                        j++;
                    }else{
                    	//멜로디가 하나라도 다르다면 비교 멈춤
                        isFind = false;
                        break;
                    }
                }
                //m이 해당 음악 악보에 포함되어있다면 비교 멈춤
                if(isFind) {
                    break;}
            }
            
            //멜로디가 포함된 음악이라면 PQ에 음악 정보(제목, 재생시간)저장
            if(isFind){
                musicPQ.offer(new Music(title, runTime));
            }
        }
        
        //PQ에 음악 정보가 저장되어있다면 맨 앞의 음악 제목을 반환
        //비어있다면 (None) 반환
        if(musicPQ.size()>0){
            answer = musicPQ.poll().title;
        }
        
        return answer;
    }
    
    //멜로디에 #이 붙은 멜로디도 비교하기 위한 멜로디 배열화 함수
    public String[] setMelody(String melody){
        Stack<String> stack = new Stack<>();
        for(char m : melody.toCharArray()){
            if(m >= 'A' && m<='Z'){
                stack.push(String.valueOf(m));
            }else{
                String s = stack.pop();
                stack.push(s+m);
            }
        }
        
        String[] arr = new String[stack.size()];
        for(int i=stack.size()-1;i>=0;i--){
            arr[i] = stack.pop();
        }
        return arr;
    }
    
    public int runTime(String startTime, String endTime){
        int h = (Integer.parseInt(endTime.substring(0,2)) - Integer.parseInt(startTime.substring(0,2)))*60;
        int m = Integer.parseInt(endTime.substring(3)) - Integer.parseInt(startTime.substring(3));
        return h+m;
    }
    
    //멜로디가 포함된 음악이 여러개라면 재생 시간이 긴 음악을 반환하기 위한 정렬 구현
    public class Music implements Comparable<Music>{
        String title;
        int runTime;
        public Music(String title, int runTime){
            this.title = title;
            this.runTime = runTime;
        }
        
        @Override
        public int compareTo(Music o){
            return o.runTime - this.runTime;
        }
    }
    
    
}

---

Result