방금그곡

https://school.programmers.co.kr/learn/courses/30/lessons/17683

프로그래머스

 

Level 2

 

빡센 구현 문제. 제시된 문자열을 포함하는 음악을 찾아야하고 추가로 중복되는 곡 중에서도 여러 조건을 확인해야한다.

 

문제로 주어지는 데이터들은 다음과 같다.

1. 찾으려는 멜로디 : "ABCDEFG"

2. 비교할 음악 예시 : "12:00,12:14,HELLO,CDEFGAB"

 

음악은 1분에 1개의 음을 재생한다. (여기서 음은 문제에 제시되는 대문자 알파벳에 + #이 추가된 문자열이다)

음악은 자신의 멜로디(예시로는 CDEFGAB)를 반복해서 재생한다. 즉, 재생시간이 멜로디 길이를 넘어가면 다시 시작한다.

주어진 두 시간은 재생이 시작된 시간과 음악이 끝난 시간이다. 

 

멜로디를 비교하는 방법은 개개인에 따라 다르기 때문에 어떠한 방식으로 구현해도 상관어 없다고 본다. 필자의 경우에는 "B#" 같이 #이 붙는 음들을 소문자 "b"로 치환해 멜로디를 커스터마이징했다. 따라서 최초에 입력받는 제시된 멜로디의 # 음들을 먼저 치환한 뒤, 이후 제시되는 문자열을 "," 로 분할하여 두 개의 시간과 음악의 제목 그리고 멜로디를 추출했다. 추출한 두 시간을 먼저 계산하여 재생 시간을 구하고, 재생 시간을 토대로 음악의 총 재생 멜로디를 구하고 치환하여 완전 탐색하여 제시된 멜로디를 포함하는지 체크하고 만약 포함한다면 재생 시간이 최대인지, 재생 시간이 같을 경우 시작 시간이 더 빠른지 비교하여 다음과 같이 정답을 반환했다. 

 

 

이후 비교 탐색은 다음과 같이 2개 의 헤더를 사용해 구현했다. 

 

 

문제 해결 아이디어는 어려운 편이 아니지만 구현 단계가 복잡하고 중간 중간 예외 처리들을 고려해야할 부분이 많은 문제라고 생각되며 너무 오래 걸리는 시간을 최대한 줄여봐야겠다...

 

public class Solution {
    static char[] melody;
    public String solution(String m, String[] musicinfos) { //방금그곡
        String answer = "(None)";
        melody = getMelody(m); //멜로디 변형 ex) B# -> b
        int maxPlayTime = 0; //멜로디를 가진 음악중 가장 오래 재생된 시간 변수
        int fastStartTime = Integer.MAX_VALUE; //멜로디를 가진 음악 중 가장 일찍 재생된 시간 변수
        for(String musicInfo : musicinfos){
            String[] splitMusicInfo = musicInfo.split(",");
            int playTime = getPlayTime(splitMusicInfo[0], splitMusicInfo[1]);
            char[] songMelody = getMelody(splitMusicInfo[3]);
            int headParam = 0; //현재 들리는 멜로디 char[] 헤더
            int headOriginal = 0; //찾으려는 멜로디 char[] 헤더
            for(int cnt = 0; cnt < playTime; cnt++){
                headParam = cnt > headParam ? cnt % songMelody.length : headParam; //현재 재생되는 시간이 멜로디 char[] 순환하게 값 조정
                char characterParam = songMelody[headParam];
                char characterOriginal = melody[headOriginal];
                if(characterParam == characterOriginal){ //현재까지는 멜로디가 맞을 경우
                    if(headOriginal == melody.length-1){ //멜로디가 완전히 맞는 경우
                        if(maxPlayTime == playTime) { //이미 찾은 음악이 있을 경우 + 재생 전체 시간도 현재 음악과 같음
                            int startTime = getStartTime(splitMusicInfo[0]);
                            if(fastStartTime > startTime) { //음악이 시작된 시간 기준으로 비교
                                fastStartTime = startTime;
                                answer = splitMusicInfo[2];
                            }
                        }else if(maxPlayTime < playTime){ //음악 전체 재생 시간으로 비교가 가능한 경우
                            maxPlayTime = playTime;
                            answer = splitMusicInfo[2];
                            if(fastStartTime == Integer.MAX_VALUE) fastStartTime = getStartTime(splitMusicInfo[0]); //초기에 비교 대상이 없어도 재생 시작 시간 입력을 위해 추가
                        }
                        break;
                    }else{
                        headOriginal++; //현재 까지는 멜로디가 맞으니 다음 멜로디 char[] index 로 이동
                    }
                }else{ //멜로디가 틀림
                    if(headOriginal != 0) cnt--; //틀렸지만 다시 처음부터 확인해야하는 경우
                    headOriginal = 0; //멜로디 맨 처음으로 되돌리기
                }
            }
        }

        return answer;
    }
    public char[] getMelody(String melodyInfo){ //멜로디 커스터마이징 char[] 로 변경한뒤 #이 달린 음들은 소문자로 치환
        String fixedMelody = "";
        for(int idx = 0; idx < melodyInfo.length(); idx++){
            if(idx == melodyInfo.length()-1){
                fixedMelody += melodyInfo.charAt(idx);
                break;
            }
            char character = melodyInfo.charAt(idx);
            char nextChar = melodyInfo.charAt(idx+1);
            if(nextChar == '#'){
                fixedMelody += (char) (character + ('a' - 'A'));
                idx++;
            }else{
                fixedMelody += character;
            }
        }
        char[] result = new char[fixedMelody.length()];
        for(int idx = 0; idx < fixedMelody.length(); idx++){
            result[idx] = fixedMelody.charAt(idx);
        }
        return result;
    }
    public int getStartTime(String startInfo){ //시작 시간 구하기, 입려된 시간*60분 + 입력된 분
        String[] startTimeInfo = startInfo.split(":");
        int startHH = Integer.parseInt(startTimeInfo[0]);
        int startMM = Integer.parseInt(startTimeInfo[1]);
        return startHH*60 + startMM;
    }
    public int getPlayTime(String startInfo, String endInfo){ //재생된 총 시간의 분 구하기
        String[] startTimeInfo = startInfo.split(":");
        String[] endTimeInfo = endInfo.split(":");
        int startHH = Integer.parseInt(startTimeInfo[0]);
        int startMM = Integer.parseInt(startTimeInfo[1]);
        int endHH = Integer.parseInt(endTimeInfo[0]);
        int endMM = Integer.parseInt(endTimeInfo[1]);
        if(startHH > endHH) {
            endHH = 23;
            endMM = 60;
        } else if (startHH == endHH && startMM > endMM) {
            endHH = 23;
            endMM = 60;
        }
        return (endHH-startHH)*60 + (endMM-startMM);
    }
}