<이분 탐색> BOJ 20191 줄임말

문제

문자열 s와 t가 주어지고 줄임말이라는 정의(b는 a의 줄임말이라고 하면 a 문자열 순서는 건드리지 않고 몇개의 문자를 제거하거나 제거하지 않았을때 b와 동일한 문자열을 만들 수 있어야 합니다)가 주어집니다. 이럴 때 문자열 t를 최소 몇개 이어붙여야 s가 줄임말이 되는 지 찾는 문제 입니다.

접근

1. t를 아무리 이어붙여도 s가 줄임말이 되지 않는 경우를 찾아야 합니다. s 문자열에 속한 문자 중 하나라도 t에 포함되지 않는 경우 t를 아무리 이어붙여도 s를 만들 수 없습니다. -1을 출력하고 함수를 종료합니다.
   • ex) s: "abc", t: "aaa"
2. t를 이어붙일 수 있는 최대 개수는 s문자열의 길이가 되겠죠. 최소 개수는 0개 이구요. 이어붙일 수 있는 개수를 기준으로 이분탐색을 돌려 줄임말이 s가 되는 최소 개수를 구합니다.

3. t를 n개 이어붙인다고 했을 때 s문자열이 줄임말이 되는지 판단해야합니다.

• 3-1. s 문자열을 가리키는 포인터와 t문자열을 가리키는 포인터를 만들어 t문자열을 가리키는 포인터에 해당하는 문자가 s문자열을 가리키는 포인터에 해당하는 문자와 동일하면 s문자열을 한칸 오른쪽으로 옮겨주고 그렇지 않다면 t문자열 포인터만 한칸 오른쪽 이동시켜줍니다. t문자열의 마지막을 가리키고 있던 경우에는 다시 0을 가리키도록 합니다. s문자열 포인터가 s문자열을 모두 한번 가리켰을 때 t문자열 탐색 횟수가 n번 이하면 true 그렇지 않으면 false를 출력합니다.
  이렇게 할 경우 시간 복잡도 $O((|S|+|T|*|S|)*log|S|)$가 되어 문제 제한을 만족하지 못합니다.
• 3-2. 이 문제의 특징을 활용합니다. 문제에서 모든 문자열을 소문자 알파벳으로만 이루어진다고 했습니다. 알파벳은 26개로 이루어져있어 모든 경우를 해보기 좋으므로 (문자열 t의 최대길이가 10만이므로 260만개를 저장하는건 충분합니다) 문자열 t의 i 인덱스부터 마지막 인덱스까지 원하는 알파벳이 처음 나오는 인덱스를 저장하는 배열을 만듭니다. 이렇게 하면 문자열t에 대한 탐색 횟수가 s문자열 길이와 동일하게 바뀌므로 매우 빠르게 가능 여부를 판단 가능합니다. 배열을 채우는 과정도 for문 밖에서 이루어지므로 전체적인 시간복잡도에 영향을 미치지 않습니다.(물론 미치긴 하지만 더해지므로)

for (int i = 0; i < 26; i++) {
  for (int j = 0; j < t.length(); j++) {
    if (t.charAt(j) == (char) ('a' + i)) {
      next[i][j] = 1;
    }
  }
  
  int nextIdx = -1;
  
  for (int j = t.length() - 1; j >= 0; j--) {
    if (next[i][j] == 1) {
      nextIdx = j;
    }
    next[i][j] = nextIdx;
  }
}

4. s문자열이 줄임말이 되는 t를 가장 적게 이어붙인 개수를 출력하면 됩니다.

코드

import java.io.*;
import java.util.*;

class Main {
    static String s;
    static String t;
    static int[][] next;

    static boolean possible(String s, String t) {
        HashSet<Character> setS = new HashSet<>();
        HashSet<Character> setT = new HashSet<>();

        for (int i = 0; i < s.length(); i++) {
            setS.add(s.charAt(i));
        }
        for (int i = 0; i < t.length(); i++) {
            setT.add(t.charAt(i));
        }
        Iterator iterator = setS.iterator();

        while (iterator.hasNext()) {
            if (!setT.contains(iterator.next())) {
                return false;
            }
        }
        return true;
    }

    static boolean check(int n) {
        int pointerS = 0;
        int pointerT = 0;

        int cnt = 0;

        while (pointerS < s.length()) {
            pointerT = next[s.charAt(pointerS) - 'a'][pointerT];
            if (pointerT == -1) {
                cnt++;
                pointerT = 0;
            } else {
                pointerT++;
                if (pointerT == t.length()) {
                    cnt++;
                    pointerT = 0;
                }
                pointerS++;
            }
        }
        if (pointerT != 0) {
            cnt++;
        }
        if (cnt > n)
            return false;

        return true;

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        s = br.readLine();
        t = br.readLine();

        if (!possible(s, t)) {
            System.out.print(-1);
            return;
        }

        next = new int[26][t.length()];

        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < t.length(); j++) {
                if (t.charAt(j) == (char) ('a' + i)) {
                    next[i][j] = 1;
                }
            }
            int nextIdx = -1;
            for (int j = t.length() - 1; j >= 0; j--) {
                if (next[i][j] == 1) {
                    nextIdx = j;
                }
                next[i][j] = nextIdx;
            }
        }

        int l = -1;
        int r = s.length() + 1;

        while (l + 1 < r) {
            int mid = (l + r) / 2;
            // System.out.println(mid);

            if (check(mid)) {
                r = mid;
            } else {
                l = mid;
            }
        }

        System.out.print(r);
    }
}