[Programmers] 방금그곡

2018 카카오 블라인드 채용 문제이다.

이문제는 문자열 찾기문제로 KMP를 사용하여 풀었다. 하지만 전처리를 해줘야할것이 많았다. 나는 일단 #을 처리하리 위해 translate라는 함수를 만들어 #이 붙은 문자들을 새로운 문자로 아예바꾸어서 문제를 해결하였다. 꼼꼼한 전처리와 KMP를 다룰 줄 알면 쉬운 문제였다.

package programmers2;
 
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution_2018카카오_방금그곡 {
    
    static class Node implements Comparable<Node>{
        int time;
        int index;
        String name;
        String music;
        
        Node(String n, String m, int t,int i){
            name=n;music=m;time=t;index=i;
        }
 
        @Override
        public int compareTo(Node o) {
            if(time==o.time) {
                return Integer.compare(index, o.index);
            }
            return -Integer.compare(time, o.time);
        }
    }
    
    public static void main(String[] args) {
//        String m ="ABCDEFG";
//        String[] musicinfos = {"12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"};
        
        String m ="ABC";
        String[] musicinfos = {"12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"};
        
//        String m ="CC#BCC#BCC#BCC#B";
//        String[] musicinfos = {"03:00,03:30,FOO,CC#B", "04:00,04:08,BAR,CC#BCC#BCC#B"};
        
        System.out.println(solution(m, musicinfos));
    }
    
    
    
    
    static String solution(String m, String[] musicinfos) {
        m=translate(m);
        
        StringTokenizer st = null;
        
        List<Node> list=new ArrayList<>();
        List<Node> result=new ArrayList<>();
        
        int index=0;
        for(String info : musicinfos) {
            st=new StringTokenizer(info,",");
            
            int time=calcTime(st.nextToken(), st.nextToken());
            String name=st.nextToken();
            
            String music=translate(st.nextToken());
            
            int loop=time/music.length();
            int remainder = time%music.length();
            
            String temp="";
            for(int i=0;i<loop;i++) {
                temp+=music;
            }
            temp+=music.substring(0,remainder);
            list.add(new Node(name,temp,time,index++));
            System.out.println(name+",,,"+temp);
        }
        
        for(Node n : list) {
            if(KMP(n.music,m)==true) {
                result.add(n);
            }
        }
 
        if(result.size()==0) {
            return "(None)";
        }
        
        Collections.sort(result);
        
        return result.get(0).name;
        
    }
    
    
    static boolean KMP(String str,String pattern) {
        int[] p = getP(pattern);
        
        int j=0;
        for(int i=0;i<str.length();i++) {
            while(j>0 && str.charAt(i)!=pattern.charAt(j)) {
                j=p[j-1];
            }
            
            if(str.charAt(i)==pattern.charAt(j)) {
                if(j==pattern.length()-1) {
                    j=p[j];
                    return true;
                }else {
                    j++;
                }
                
            }
        }
        
        return false;
    }
    
    static int[] getP(String pattern) {
        int[] p =new int[pattern.length()];
        
        int j=0;
        for(int i=1;i<pattern.length();i++) {
            while(j>0 && pattern.charAt(i)!=pattern.charAt(j)) {
                j=p[j-1];
            }
            
            if(pattern.charAt(i)==pattern.charAt(j)) {
                j++;
                p[i]=j;
            }
        }
        
        return p;
    }
    
    
    static int calcTime(String start,String end) {
        StringTokenizer st = null;
        st=new StringTokenizer(start,":");
        int startTime = Integer.parseInt(st.nextToken())*60 + Integer.parseInt(st.nextToken());
        
        st=new StringTokenizer(end,":");
        int endTime = Integer.parseInt(st.nextToken())*60 + Integer.parseInt(st.nextToken());
        return endTime-startTime;
    }
    
    
    static String translate(String m) {
        String result="";
        for(int i=0;i<m.length();i++) {
            if(m.charAt(i)=='#') {
                result=result.substring(0,result.length()-1);
                if(m.charAt(i-1)=='C') {
                    result+="L";
                }else if(m.charAt(i-1)=='D') {
                    result+="M";
                }else if(m.charAt(i-1)=='F') {
                    result+="N";
                }else if(m.charAt(i-1)=='G') {
                    result+="O";
                }else if(m.charAt(i-1)=='A') {
                    result+="P";
                }
            }else {
                result+=m.charAt(i);
            }
            
        }
        return result;
    }
}