[백준 20191번] 줄임말

문제 링크: 20191번 제목

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

 

문제에서의 S를 target이라 하고, T를 pattern이라 하자. alphas는 리스트의 배열로서, alphas[c]라는 리스트는 c라는 문자가 target에서 어디에 위치하는지에 대해 그 인덱스를 모두 담고 있다. 한편 patIdx라는, pattern을 가리키는 인덱스를 하나 둔다. 이는 pattern에서 마지막으로 사용된 문자의 위치를 가리키고 있으며, 초기값은 -1로 해둔다. 이는 뒤에 가서 그 이유를 알 수 있다.

우리는 for문 내에서 target을 한 글자씩 cur이라는 변수로 두고 채워나가는데, patIdx보다 뒤에 있는 문자만 사용 가능하다. 즉 alphas[cur]에서 patIdx보다 큰 최소인 값을 구하면, pattern에서 해당 인덱스의 문자가 cur을 채우는 것이다.

만약 찾지 못했다면 어떻게 해야할까? 그러면 pattern을 한 번 더 붙이는 상황이 온다. 우리가 이것을 실제로 concat할 필요는 없고, patIdx를 0으로 바꾸어 다시 한 번 patIdx보다 큰 최소인 값을 구하는 과정을 반복한다.

그리고 탐색 과정은 이분탐색(이게 lower bound인가?)을 사용함으로써 시간복잡도를 최소로 할 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int binarySearch(List<Integer> list, int key) {
    // key보다 큰 최소인 정수 반환
        int left = 0;
        int right = list.size() - 1;
        int mid = (left + right) / 2;

        while (left <= right) {
            mid = (left + right) / 2;

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

        if (left < list.size())
            return list.get(left);
        else
            return -2;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String target = br.readLine(); // 만들어야 하는 문자열
        String pattern = br.readLine(); // 붙여나갈 문자열

        // alphas
        List<Integer>[] alphas = new ArrayList['z'-'a'+1];
        for (int i = 0; i < 'z'-'a'+1; i++) {
            alphas[i] = new ArrayList();
        }
        for (int i = 0; i < pattern.length(); i++) {
            char cur = pattern.charAt(i);
            alphas[cur - 'a'].add(i);
        }

        int n = 1;
        int patIdx = -1;
        for (int i = 0; i < target.length(); i++) {
            char cur = target.charAt(i);

            // 해당하는 문자가 아예 없는 경우
            if (alphas[cur-'a'].size() == 0) {
                n = -1;
                break;
            }

            // patIdx보다 큰 최소인 수를 찾음
            patIdx = binarySearch(alphas[cur-'a'], patIdx);
            if (patIdx == -2) {
                n++;
                patIdx = alphas[cur-'a'].get(0);
            }
        }

        System.out.println(n);
    }
}