[JAVA] 백준 20191 - 줄임말

1. 문제

https://www.acmicpc.net/problem/20191

20191번: 줄임말

2. 해결 방법

• 문제에서 주어진 S, T의 길이가 매우 길기 때문에 S * T 방식으로 접근하면 시간초과 발생
• 문자열 S는 한번씩 돌면서 단어를 찾아야 하기 때문에 여기서는 시간을 줄일 수 없음
• 따라서 T에서 시간을 줄여야 함 => 이진탐색 사용
• 입력으로 S = abbcca, T = cbca가 들어왔다고 가정해보자

1. T의 각 문자별로 위치들을 담고있는 ArrayList 생성 (인덱싱 => a = 0, b = 1, ..., z = 25)
   • arr[ a ] = 3
   • arr[ b ] = 1
   • arr[ c ] = 0, 2
2. 문자열 S를 순서대로 돌며 한 문자씩 판단 ( index = -1, ans = 1 로 시작 )
   1. 맨 처음에 a를 찾아야 함 => index = 3
   2. 다음에는 b를 찾아야 함 => arr[b]의 마지막 값이 index 값보다 작음 (이는 T를 하나 추가해야 됨을 의미)
   3. ans증가 후 index에는 arr[b]의 맨 처음 값을 넣어줌 (ans = 2, index = 1)
   4. 다음에는 다시 b를 찾아야 함 => arr[b]의 마지막 값이 index와 같음 (같으면 쓴것이기 때문에 T 추가)
   5. ans증가 후 index에는 arr[b]의 맨 처음 값을 넣어줌 (ans = 2, index = 1)
   6. 다음에는 c를 찾아야 함 => arr[c]의 마지막 값이 index보다 큼 (이는 T 추가 없이 가능하다는 의미)
   • 여기서 이진탐색이 필요
     • arr[c]에서 현재 index인 1보다 크면서 가장 작은값을 이진탐색으로 찾음
     • 찾은 결과 2를 index에 넣어줌 (index = 2, ans = 2)
     • 이 작업을 문자열 S 길이만큼 반복 후, ans(사용한 T의 개수) 출력

• 시간 복잡도 : S의 길이(1,000,000) * log(T의 길이(100,000)) < 1초

3. 코드

import java.util.ArrayList;
import java.util.Scanner;

public class p20191 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String target = sc.nextLine();
        String str = sc.nextLine();
        // str로 target을 만들어야 됨

        ArrayList<Integer>[] positionList = new ArrayList[26];
        for(int i = 0 ; i < str.length() ; i ++) {
            char c = str.charAt(i);
            int charToInt = c - 'a';

            if(positionList[charToInt] == null) {
                positionList[charToInt] = new ArrayList<>();
            }
            positionList[charToInt].add(i);
        }

        int index = -1;     // 현재 str의 몇번째에 있는지
        int ans = 1;        // str을 몇개 썻는지
        for(int i = 0 ; i < target.length() ; i ++) {
            char c = target.charAt(i);
            int charToInt = c - 'a';

            // 나와야 되는 문자가 str에 한번도 없는 경우
            if(positionList[charToInt] == null) {
                ans = -1;
                break;
            } else {
                // 직전에 str에서 사용한 문자 이후에 만들어야 되는 문자가 나오지 않는 경우
                // 만들어야 되는 문자의 가장 첫번째 위치를 index로 지정, ans ++
                if(positionList[charToInt].get(positionList[charToInt].size() - 1 ) <= index) {
                    ans ++;
                    index = positionList[charToInt].get(0);
                } else {
                    // 이 상황에서는 index보다는 크지만, str에서 가장 먼저 나오는 문자를 찾아야 됨
                    index = search(index, 0, positionList[charToInt].size() - 1, positionList[charToInt]);
                }
            }
        }

        System.out.println(ans);
    }

    // list에서 index보다 크면서 가장 작은 값 찾기
    static int search(int index, int left, int right, ArrayList<Integer> list) {
        while(left < right) {
            int mid = (left + right) / 2 + 1;

            if(list.get(mid) > index && list.get(mid - 1) <= index ) {
                return list.get(mid);
            } else if(list.get(mid) > index && list.get(mid - 1) >= index) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return list.get(left);
    }
}