[백준] 1062번 가르침 Java 풀이

PROBLEM

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

SOLUTION

문제를 이해하는데 조금 시간이 걸렸었는데 핵심은 K개의 글자를 배웠을 때, 만들 수 있는 단어 개수의 최대값을 찾는 것이다. 따라서 K개의 글자를 선택(조합)하고, 각 단어들을 만들 수 있는지 확인하고, 가장 많은 단어를 만들 수 있는 경우를 찾아낸다.

먼저, K개의 글자를 조합하기 전에 이미 포함되어 있는 글자들이 있다. 남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다.와 같이 a, c, i, t, n은 반드시 포함되어 있어야한다.

조합한 K개의 글자들에 대해서 각 단어들을 만들 수 있는지 확인해야 한다. 이 때, 최악의 경우 시간복잡도를 고려하지 않을 수 없다. 현재 조합 개수는 26개의 알파벳 중 5개를 반드시 포함해야하므로 제외하고, $ _{26-5} \mathrm{ C } _{K-5} $ 이다. 최대 경우의 수는 $ _{21} \mathrm{ C } _{10} = 352,716 $ 이다.

조합을 완성한 후에 각 조합마다 각 단어들을 비교한다. 단어의 최대 개수 50개와 단어의 최대 길이 15개를 고려했을 때 $ 352,716 \times 50 \times 15 = 264,537,000 $ 이므로 이는 시간 초과가 날 것이다.

단어 별로 알파벳의 순서나 빈도수는 중요하지 않고 특정 알파벳이 등장했는지 안 했는지가 중요하므로 각 알파벳의 유무를 나타내는 비트마스킹을 사용하면 시간을 줄일 수 있다. 위에서 단어의 길이만큼 비교하는 연산 대신에 비트 연산을 통해 한 번에 비교하므로 연산 횟수는 $ 352,716 \times 50 = 17,635,800 $ 로 줄어든다. 이 정도면 충분히 계산 가능하다.

  1. 모든 단어는 a, c, i, t, n를 포함하므로 K가 5보다 작다면 읽을 수 있는 단어는 없다. 0을 출력하고 종료한다.
  2. 입력된 단어들을 비트마스킹 한다.
  3. a, c, i, t, n을 포함하고, K-5개의 다른 알파벳을 조합한다.
  4. 조합된 알파벳과 각 단어들을 비교(비트 연산)하며 읽을 수 있는 단어의 개수를 센다.
  5. 최대값을 출력한다.

비트마스킹

여러 개의 boolean 형 상태를 저장하는데 유용하다. &, |, ! 등을 적절히 활용하여 상태를 조작하고, 비교할 수 있다. 이 문제에서는 각 알파벳의 유무를 이진형태로 저장하여 사용하고 있다. 여기서 비트 연산을 활용하는 부분은 2가지이다.

처음 입력된 각 단어를 비트마스킹할 때 소스코드는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

private static long[] strToBitmask(String[] arr) {
  long[] result = new long[arr.length];

  for (int i=0; i<arr.length; i++) {
    char[] ca = arr[i].toCharArray();
    long l = 0L;
    for (char c : ca)
      l = (l | (1 << c-'a'));

    result[i] = l;
  }

  return result;
}

여기서 핵심은 l = (l | (1 << c-'a')); 이 부분인데, |(or)연산을 통해 특정 알파벳의 유무를 저장하는 것이다. 만약 단어가 “tabad”이고 “taba”까지 실행되었다고 하면 l에는 아래와 같이 저장되어야 한다.

  z y ... t ... d c b a
l   0 0 ... 1 ... 0 0 1 1

이 상태에서 다음 ‘d’에 대해서 |(or)연산하면 아래와 같다. 1 << c-'a' 에서 c가 ‘d’이므로 $ 1000 _{(2)} $ 이다.

  z y ... t ... d c b a
l 0 0 ... 1 ... 0 0 1 1
1 << `c-'a' 0 0 ... 0 ... 1 0 0 0
  0 0 ... 1 ... 1 0 1 1

다음 비트마스킹을 사용하는 부분은 비트마스킹된 각 단어와, 조합으로 만들어진 알파벳들의 비트마스킹을 비교할 때이다. 소스코드는 아래와 같다.

1
2
3
4
5
6
7
8
9

private static int compareBitmaskWord(long bitmaskV) {
  int result = 0;

  for (int i=0; i<bitmaskWord.length; i++)
    if ((bitmaskWord[i] & bitmaskV) == bitmaskWord[i])
      result++;

  return result;
}

bitmaskV는 조합 결과인 visited[]을 비트마스킹한 것이다. 여기서 핵심은 (bitmaskWord[i] & bitmaskV) == bitmaskWord[i]인데, &(and)연산을 통해서 각 단어가 가진 알파벳을 bitmaskV가 가지고 있는지 확인한다. 모두 가지고 있다면 &(and)연산 결과가 해당 단어의 비트마스킹과 같아야 한다.

예를 들어, 단어가 “abd”이고 조합 결과가 “abcdf”라 하면 아래와 같이 비트마스킹할 수 있고, &(and)연산 결과는 1011로 해당 단어인 “abd”와 같다는 것을 알 수 있다. 즉, bitmaskV가 가진 알파벳이 bitmaskWord[i]가 가진 알파벳을 포함하고 있는지를 확인할 수 있다.

  ... f e d c b a
bitmaskWord[i] ... 0 0 1 0 1 1
bitmaskV ... 1 0 1 1 1 1
  ... 0 0 1 0 1 1

마지막으로, 비트마스킹한 값들을 long형으로 저장하여 사용하고있다. 각 알파벳의 유무를 저장하므로 26자리 필요한데, int형도 32비트이므로 알파벳의 유무를 표현하기에 충분하다. long대신 int를 써도 무방하다.

SOURCE CODE (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

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

public class Main {
  static int N, K, answer;
  static long[] bitmaskWord;

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

    stk = new StringTokenizer(br.readLine());
    N = Integer.parseInt(stk.nextToken());
    K = Integer.parseInt(stk.nextToken());

    String[] arr = new String[N];
    for (int i=0; i<N; i++) {
      arr[i] = br.readLine();
    }

    if (K < 5) {
      System.out.println(0);
      return;
    }

    bitmaskWord = strToBitmask(arr);

    boolean[] visited = new boolean[26];

    // a b c d e f g h i j k  l  m  n  o  p  q  r  s  t  u  v  w  x  y  z
    // 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
    // a, c, i, t, n 포함
    visited[0] = true;
    visited[2] = true;
    visited[8] = true;
    visited[13] = true;
    visited[19] = true;
    // 5개를 포함한 조합 생성
    comb(5, 0, visited);

    System.out.println(answer);
  }

  private static void comb(int cnt, int start, boolean[] visited) {
    if (cnt == K) {
      long bitmaskV = visitedToBitmask(visited);
      int result = compareBitmaskWord(bitmaskV);
      answer = Math.max(answer, result);

      return;
    }

    for (int i=start; i<26; i++) {
      if (visited[i])
        continue;

      visited[i] = true;
      comb(cnt+1, i+1, visited);
      visited[i] = false;
    }
  }

  private static int compareBitmaskWord(long bitmaskV) {
    int result = 0;

    for (int i=0; i<bitmaskWord.length; i++)
      if ((bitmaskWord[i] & bitmaskV) == bitmaskWord[i])
        result++;

    return result;
  }

  private static long visitedToBitmask(boolean[] visited) {
    long result = 0L;

    for (int i=0; i<visited.length; i++)
      if (visited[i])
        result = (result | (1 << i));

    return result;
  }

  private static long[] strToBitmask(String[] arr) {
    long[] result = new long[arr.length];

    for (int i=0; i<arr.length; i++) {
      char[] ca = arr[i].toCharArray();
      long l = 0L;
      for (char c : ca)
        l = (l | (1 << c-'a'));

      result[i] = l;
    }

    return result;
  }
}

OFF THE RECORD

처음에 로직을 구상하고 코드로 구현하고 제출했을 때 시간초과가 났다. 20분정도 시간을 줄일 방법을 찾으며 헤메다 알게된 사실은 조합 로직이 들어갈 부분에 순열처럼 구현을 해놓았던 것이다. 그러니 시간이 초과할 수 밖에 없지.

댓글 남기기

관련있는 다른 게시글