프로그래머스 Lv.2) 방금그곡

2018 KAKAO BLIND RECRUITMENT [3차]

방금그곡

코딩테스트 연습 - [3차] 방금그곡

풀이

꽤나 까다로운 문제였다. 악보에 사용되는 음이 A,B,C 단순 문자와 함께 올림표가 포함된 C#,D# 이런 문자가 함께 있어서 그런 것 같다..

다른 분들은 음표를 변형해서 풀었다는 글도 보았고, 쉽게 푸신분도 있다고 하는 것 같은데 나는 그렇지 않았다.

 

먼저 테스트 케이스에서 계속 실패하던 부분을 살펴보면,

1. 처음 음악의 악보를 저장할 때, 올림표가 포함된 악보 저장을 제대로 해주지 못한점.

2. 네오가 기억하는 멜로디인 String m을 노래의 한 부분에서 찾아주려고 할 때, 올림표가 붙어있는 음표들을 제대로 잘라주지 못한 점

3. 찾을 수 없는 값에 대해 (None) 을 리턴해주어야 하는데 문제만 보고 '(None)'을 리턴해준 점.

 

이정도가 되겠다. 나머지는 크게 어렵게 생각하지 않은 문제점이었다.

 

내가 푼 로직은 다음과 같다.

1. 음악의 정보를 저장할 Music 클래스를 만들고, 우선순위 큐에 저장될 때 재생시간이 긴 순서대로, 재생시간이 같은 경우에는 먼저 들어온 음악이 먼저 저장되도록 설정한다(CompareTo 부분).

 1-1. 재생 시간 저장은 HH:MM 형식이어서, split을 통해 시간*60 + 분 으로 시작시간과 종료시간을 구해주고, 차이를 저장해줬다.

 1-2. 악보를 저장할 때는 올림표가 있는지 확인하고, 올림표 수만큼 악보의 length에서 빼주었다. (C#은 하나의 음표인데, String에는 올림표가 한자리를 차지하고 있기 때문에 빼주었다.)

 1-3. while문을 통해 play 시간만큼 음표를 붙여주었다. (여기서도 올림표에 주의할 것, getNote부분을 보시면 됩니다.)

 1-4. 네오가 기억하고 있는 멜로디가 해당 음악의 한 부분인지 체크하는 isPart 메소드를 만들어 검증하였다. 이미 올림표를 포함한 길이만큼 음악 악보가 저장되어있기 때문에, 네오가 기억하는 멜로디에서 올림표 처리를 하지 않았다. 다만, 네오가 기억하는 멜로디만큼 악보의 문자열을 자를 때, 마지막 잘린 부분 뒤에 # (올림표)가 있는지는 체크해주어야 한다. (기억하는 멜로디 : ABC 음악 악보 : ABC#의 경우, 악보에서 ABC만 잘리는 경우가 발생 방지)

2. 우선순위 큐에 저장된 음악을 돌면서 조건에 부합하는 음악을 answer에 저장하고 탐색을 마친다. (부합하는 음악이 없다면 초기화 때 저장한 (None)이 바뀌지 않음)

 

코드

import java.util.PriorityQueue;

class Solution {
    public String solution(String m, String[] musicinfos) {
        String answer = "(None)";
        PriorityQueue<Music> pq = new PriorityQueue<>();
        for(String info : musicinfos) {
            String[] infoArr = info.split(",");
            pq.offer(new Music(infoArr[0],infoArr[1],infoArr[2],infoArr[3]));
        }
        
        while(!pq.isEmpty()) {
            Music music = pq.poll();
            if(music.isPart(m)) {
                answer = music.name;
                break;
            }
            
        }
        
        return answer;
    }
}

class Music implements Comparable<Music>{
    private final char SHARP = '#';
    int playTime;
    String note;
    String name;
    
    public Music(String startTime, String endTime, String name, String notes) {
        this.name = name;
        this.playTime = getTime(endTime) - getTime(startTime);
        this.note = getNote(notes, this.playTime);
    }
    
    public int getTime(String timeStr) {
        String[] timeArr = timeStr.split(":");
        int hour = Integer.parseInt(timeArr[0]);
        int min = Integer.parseInt(timeArr[1]);
        
        return hour*60 + min;
    }
    
    public String getNote(String notes, int time) {
        StringBuffer sb = new StringBuffer();
        int len = notes.length();
        int remain = time;
        
        if(notes.replaceAll("[^#]","").length() !=0) {
            len -= notes.replaceAll("[^#]","").length();
        }
        
        while(remain > 0) {
            if(remain -len >=0) {
                sb.append(notes);
                remain-= len;
            } else {    // 잔여 횟수가 len보다 적게 남았으면
                for(int i=0; i<notes.length(); i++) {
                    char ch = notes.charAt(i);
                    if(ch != SHARP) {
                        sb.append(ch);
                        remain--;
                    } 
                    if(i+1 < notes.length()) {
                        if(notes.charAt(i+1) == SHARP) {
                            sb.append(SHARP);
                        }
                    }
                    if(remain ==0) {
                        break;
                    }
                }
            }
        }
        return sb.toString();
    }
    
    public boolean isPart(String str) {
        boolean result = false;
        int len = str.length();
        for(int i=0; i<=this.note.length()-len; i++) {
            StringBuffer part = new StringBuffer(this.note.substring(i,i+len));

            if(i+len < this.note.length()) {
                if(this.note.charAt(i+len) == SHARP) {
                    part.append(SHARP);
                }
            }
            if(part.toString().equals(str)) {
                result = true;
                break;
            }
        }
        return result;
    }
    
    @Override
    public int compareTo(Music m) {
        return this.playTime <= m.playTime ? 1 : -1;
    }
}