백준 34348번: snupc 문자열 (Easy) Java Solution

1. Problem Definition & Analysis

$f(k) =$ s$\times$$k +$n$\times$$k +$u$\times$$k +$p$\times$$k +$c$\times$$k$ 이다. 시작 지점($l$), 종료 지점($r$)을 담은 $Q$개 만큼의 쿼리가 주어진다. 문자열의 해당 구간에 있는 문자들을 순서를 변경하지 않고 추출하여 $f(k)$를 만들 수 있다고 할 때, $k$의 최댓값을 구하는 문제이다.

기본적으로 각각의 문자가 등장한 횟수를 누적합 배열로 관리하지만, 문자열 $f(k)$에서 현재 문자가 $k$번 등장하기 전까지 등장한 다음 문자들은 아무 의미를 갖지 않는다. 즉, s, n, u, p, c 각각의 문자는 이전의 문자가 $k$번 등장하기 전에는 uncountable하다.

예를 들어 $k = 3$인 조건에서 $3$번째 s 문자가 발견된 첫 번째 지점이 $i = 5$라고 하자. 해당 지점까지 등장한 n 문자의 개수는 $0$개일 수도, $1$개일 수도, $2$개일 수도 있다. 하지만 그것은 상관없다. 만약 n 문자가 $1$번 등장했다면 $4$번째 n 문자가 발견된 첫 번째 지점을 찾으면 되고, $2$번 등장했다면 $5$번째 n 문자가 발견된 첫 번째 지점을 찾으면 된다. 이런 식으로 c 문자까지 다음 문자를 탐색하고자 하는 지점($i$)의 개수 값으로부터 $k$개만큼 증가한 개수를 갖는 첫 번째 지점이 어디인지 찾으면 된다.

그런데 여기서 해당 문자가 $sum[i] + k$개만큼 등장한 지점을 선형 탐색으로 찾으면 Naive Algorithm과 같은 시간 복잡도($O(Q \times L \times k)$)를 갖게 된다.

먼저 누적합 배열의 값들이 정렬되어 있다는 성질을 활용해 $sum[i] + k$가 저장된 지점을 이진 탐색으로 찾으면 시간 복잡도를 $O(Q \times \log{L} \times k)$로 개선할 수 있고, $k$가 최대 $20,000$까지의 값을 가질 수 있으므로 $k$를 찾는 것 또한 이진 탐색으로 찾으면 시간 복잡도를 $O(Q \times \log{L} \times \log{k})$까지 개선할 수 있다. 이 경우엔 $Q$의 크기에 따라 누적합 배열 초기화 로직의 시간 복잡도인 $O(L)$이 지배적일 수 있다.

2. Solution

package P34348;

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

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static String line;
    static int Q, l, r;
    static int[] s, n, u, p, c;
    static char[] chars = new char[]{'s', 'n', 'u', 'p', 'c'};

    public static void main(String[] args) throws IOException {
        line = br.readLine();
        s = new int[line.length() + 1];
        n = new int[line.length() + 1];
        u = new int[line.length() + 1];
        p = new int[line.length() + 1];
        c = new int[line.length() + 1];
        for (int i = 1; i <= line.length(); i++) {
            s[i] = s[i - 1] + ((line.charAt(i - 1) == 's') ? 1 : 0);
            n[i] = n[i - 1] + ((line.charAt(i - 1) == 'n') ? 1 : 0);
            u[i] = u[i - 1] + ((line.charAt(i - 1) == 'u') ? 1 : 0);
            p[i] = p[i - 1] + ((line.charAt(i - 1) == 'p') ? 1 : 0);
            c[i] = c[i - 1] + ((line.charAt(i - 1) == 'c') ? 1 : 0);
        }

        Q = Integer.parseInt(br.readLine());
        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            l = Integer.parseInt(st.nextToken());
            r = Integer.parseInt(st.nextToken());
            sb.append(solve()).append('\n');
        }

        System.out.println(sb);
    }

    public static int solve() {
        int low = 1, high = (r - l + 1) / 5 + 1, ret = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (DFS(l - 1, mid, 0)) {
                ret = Math.max(ret, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ret;
    }

    public static boolean DFS(int i, int k, int depth) {
        if (depth == 5)
            return true;

        switch (chars[depth]) {
            case 's':
                i = binarySearch(s, i, r, s[i] + k);
                break;
            case 'n':
                i = binarySearch(n, i, r, n[i] + k);
                break;
            case 'u':
                i = binarySearch(u, i, r, u[i] + k);
                break;
            case 'p':
                i = binarySearch(p, i, r, p[i] + k);
                break;
            case 'c':
                i = binarySearch(c, i, r, c[i] + k);
                break;
        }
        if (i < 0)
            return false;

        return DFS(i, k, depth + 1);
    }

    public static int binarySearch(int[] arr, int l, int r, int target) {
        int ret = Integer.MAX_VALUE;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] > target) {
                r = m - 1;
            } else if (arr[m] < target) {
                l = m + 1;
            } else {
                ret = Math.min(ret, m);
                r = m - 1;
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }
}

핵심 로직만 빠르게 살펴보겠다.

        for (int i = 1; i <= line.length(); i++) {
            s[i] = s[i - 1] + ((line.charAt(i - 1) == 's') ? 1 : 0);
            n[i] = n[i - 1] + ((line.charAt(i - 1) == 'n') ? 1 : 0);
            u[i] = u[i - 1] + ((line.charAt(i - 1) == 'u') ? 1 : 0);
            p[i] = p[i - 1] + ((line.charAt(i - 1) == 'p') ? 1 : 0);
            c[i] = c[i - 1] + ((line.charAt(i - 1) == 'c') ? 1 : 0);
        }

문자열을 입력받으면 누적합 배열을 초기화한다.

    public static int binarySearch(int[] arr, int l, int r, int target) {
        int ret = Integer.MAX_VALUE;
        while (l <= r) {
            int m = (l + r) / 2;
            if (arr[m] > target) {
                r = m - 1;
            } else if (arr[m] < target) {
                l = m + 1;
            } else {
                ret = Math.min(ret, m);
                r = m - 1;
            }
        }
        return ret == Integer.MAX_VALUE ? -1 : ret;
    }

누적합 배열에서 매개변수로 주어진 값(target)이 처음으로 등장하는 위치를 찾기 위한 사용자 정의 이진 탐색 알고리즘이다.

    public static boolean DFS(int i, int k, int depth) {
        if (depth == 5)
            return true;

        switch (chars[depth]) {
            case 's':
                i = binarySearch(s, i, r, s[i] + k);
                break;
            case 'n':
                i = binarySearch(n, i, r, n[i] + k);
                break;
            case 'u':
                i = binarySearch(u, i, r, u[i] + k);
                break;
            case 'p':
                i = binarySearch(p, i, r, p[i] + k);
                break;
            case 'c':
                i = binarySearch(c, i, r, c[i] + k);
                break;
        }
        if (i < 0)
            return false;

        return DFS(i, k, depth + 1);
    }

s부터 c까지 $k$개씩 찾아 $f(k)$가 존재하는지 검사하기 위한 DFS 로직이다.

    public static int solve() {
        int low = 1, high = (r - l + 1) / 5 + 1, ret = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (DFS(l - 1, mid, 0)) {
                ret = Math.max(ret, mid);
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return ret;
    }

$k$의 최대값을 이진 탐색한다.

3. Conclusion

        switch (chars[depth]) {
            case 's':
                i = binarySearch(s, i, r, s[i] + k);
                break;
            case 'n':
                i = binarySearch(n, i, r, n[i] + k);
                break;
            case 'u':
                i = binarySearch(u, i, r, u[i] + k);
                break;
            case 'p':
                i = binarySearch(p, i, r, p[i] + k);
                break;
            case 'c':
                i = binarySearch(c, i, r, c[i] + k);
                break;
        }

이 문제의 핵심이 되는 기존 문자가 $k$번 등장하기 전까지 등장한 다음 문자들은 아무 의미를 갖지 않는다는 발상과, 그것을 누적합과 이진 탐색 알고리즘을 활용해 구현하는 데까지 이르는 과정이 결코 쉽지 않다. 아직 제출한 사람도 35명밖에 없는 따끈따끈한 문제여서 평균 골드 2로 기여되어 있는데 다소 저평가되어 있다고 생각한다.