[백준 16677] 악마 게임

 

원래 단어와 사전의 단어를 각각 가리키는 포인터를 둔다.

 

D	E	V	I	L	I	V
D	E	V	I	L	I	V	I

 

시작시 포인터위치는 양쪽 다 0이며 D, D를 비교한다.

 

D	E	V	I	L	I	V
D	E	V	I	L	I	V	I

일치시에 양 포인터가 오른쪽으로 한칸 움직인다.

D, E, V, I, L, I, V가 모두 일치하므로 포인터는 7번째 문자를 가리킨다.

 

원래단어의 포인터가 끝위치일때는 사전단어의 포인터만 움직이며 갑분싸 가성비가 그만큼 줄어든다.

 

 

다른 예시를 보자

D	E	V	I	L	I	V
D	E	N	V	E	R

포인터가 3번째 위치일때 글자가 서로 다르다.

이럴때는 사전단어의 포인터 위치만 증가하며 맞을때까지 움직인다.

단어가 일치하지 않으므로 갑분싸 가성비는 감소한다.

 

원래 단어 3번째, 사전 단어 4번째일때 일치하게 되는데, 이때 위 예시와 마찬가지로 양 포인터가 움직인다.

 

 

사전단어의 끝부분까지 포인터가 도달했을때 탐색이 종료되는데 원래단어의 포인터가 끝부분에 있다면

갑분싸 단어로 사용할 수 있다.

 

사용할 수 있는 단어를 모두 구했다면 갑분싸 가성비 내림차순으로 정렬하여 가장 큰 값을 구하면 된다.

점수의 자료형은 실수형으로 하여 소수점 값까지 구해주어야 정확히 정렬할 수 있다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String m = sc.next();
        int n = sc.nextInt();
        
        Dictionary dic[] = new Dictionary[n];
        for(int i=0; i<n; i++) {
            String name = sc.next();
            double level = sc.nextInt();
            dic[i] = new Dictionary("No Jam", 0);
            
            int left = 0;
            int right = 0;
            double k = 0;
            while(true) {
                if(right == name.length()) break;
                if(left == m.length()) {
                    right++;
                    k++;
                } else {
                    if(m.charAt(left) == name.charAt(right)) {
                        left++;
                        right++;
                    } else {
                        right++;
                        k++;
                    }
                }
            }
            
            if(left == m.length()) {
                dic[i].name = name;
                dic[i].level = level/k;
            }
        }
        
        Arrays.sort(dic);
        
        System.out.println(dic[0].name);
    }
    
    static class Dictionary implements Comparable<Dictionary> {
        String name;
        double level;
        
        Dictionary(String name, double level) {
            this.name = name;
            this.level = level;
        }
        
        public int compareTo(Dictionary d) {
            if(this.level > d.level)
                return -1;
            else if(this.level == d.level)
                return 0;
            else return 1;
        }
    }
}