[백준 - 8338번] Type Two de Bruijn Sequences - Java

문제 링크

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

문제

티어: 골드 1
알고리즘: 그리디, 애드 혹

입력

표준 입력의 첫 번째 줄에는 두 개의 정수 m과 n이 공백 하나로 구분되어 주어집니다. (1 ≤ m, n ≤ 1,000,000)

두 번째 줄에는 공백이 없는 길이 m의 0과 1로 구성된 문자열 s가 주어집니다.

출력

표준 출력의 첫 번째 줄에 s가 n차 유형 2 de Bruijn 시퀀스가 되기 위해 끝에 추가해야 하는 최소 숫자의 개수를 나타내는 0 이상의 정수를 출력합니다.

풀이

s가 n차 유형 2 de Bruijn 시퀀스가 되기 위해 끝에 추가해야 하는 최소 숫자의 개수를 출력해야 한다.

s가 만약 빈 문자열이고, n이 3이라면 최선의 시퀀스는 어떻게 될까?
010101이 된다.

왜냐하면 불필요한 것은 제거하고, 필요한 것만 담았기 때문이다.

그러면 왜 010101이 필요한 것만 담은 문자열일까?

모든 길이 3인 문자열을 포함하기 위해서는 각 자리의 문자가 0, 1을 둘 다 선택할 수 있어야 한다.

그래야 0 0 0, 0 0 1, 0 1 0, 1 0 0, ..., 1 1 1을 전부 포함할 수 있기 때문이다.

자리마다 01 or 10이 필요하다는 것을 알 수 있다.

그래서 자리마다 01 or 10이 필요하며, 3차 유형 2 de Bruign 시퀀스는 010101이 되는 것이다.

이 해법을 알았다면, 구현은 간단하다.

s의 01 or 10 set이 몇 개 있는지 세는 것이다. (cnt)

그 set은 총 n개 있어야 하기 때문에 답은 n * 2 - cnt가 된다.

주의할 점은 s에서 set이 아닌 1이나 0이 마지막 set 이후에 존재하는 경우 이어서 set을 만들어야 한다.

예를 들어 01011인 경우 마지막 1은 set이 아니기 때문에 이어서 0을 붙여주면 01011/0이 3차 최적해가 된다.

이 풀이의 시간 복잡도는 O(m)이다.

소스 코드

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int m = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());
      
      String input = br.readLine();
      int cnt = 0;
      ArrayList<Integer> list = new ArrayList<>();
      for(int i=0; i<input.length(); i++) {
          if(list.size() == 0) {
              cnt += 1;
              list.add(input.charAt(i) - '0');
          } else if(list.size() == 1) {
              if(list.get(0) != (input.charAt(i) - '0')) {
                  cnt += 1;
                  list = new ArrayList<>();
              }
          }
      }
      int answer = n * 2 - (cnt);
      System.out.println(answer > 0 ? answer : 0);
  }
}