BOJ) 가르침 (1062 번)

가르침

1062번: 가르침

모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다.

어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 구하는 문제다.

 

단어는 모두 소문자로 주어지고,  1 <= N <= 50,  0 <= K <= 26 , 8 <= 모든 단어의 길이 <= 15 라는 조건이 주어졌다.

 

알고리즘 분류가 브루트포스, 비트 마스킹,  백트래킹으로 되어있다.

위의 알고리즘들을 이용해서 이 문제를 풀었다.

 

우선, 모든 단어의 시작 prefix와 끝인 suffix에 5 글자가 존재하기 때문에 k를 입력받을 때, 미리 -5를 해주었다. (anta, tica ~> a, c, i, n, t)

그리고, overflow를 방지하기 위해 boolean 배열인 check를 위의 다섯 글자를 가지고 초기화해주었다.

사실, 이 부분도 비트마스크로 해결할 수는 있지만, 조금 더 직관적이길 바래서 boolean을 택했다.

또한, 가르쳐줄 글자 a ~ z의 값을 0 ~ 26으로 정해두고 비트마스크를 설정해주었다.

default인 다섯 글자를 먼저 생성해주고, 나머지 k-5 개의 순열을 구해주었다.

 

순열을 구할 때는 a~z인 0~26을 돌면서 이미 bitmask에 들어있는지 확인하고, 비트 마스킹이 안돼있으면 새롭게 추가하면서 재귀적으로 탐색하게 만들어 주었다. 탐색이 끝난 후, 돌아왔을 때는 다른 순열에서 이 값이 포함되어 있으면 안되기 때문에 false로 바꿔주어 백트래킹 설정을 해줬다.

이 재귀 메소드를 돌면서 k-5개 만큼 추가해주었으면, 몇 개의 단어가 비트마스크 글자로 읽을 수 있는지 값을 구해주었다.

 

처음 단어를 저장할 때부터 비트마스크로 저장해두어서 연산 횟수를 줄여주었다.

이 비트마스크 단어 배열을 돌면서, 위에서 구한 비트마스크와 AND 연산 (&)을 통해 해당 단어를 읽을 수 있는지 판별해주어 MAX 값을 최신화 해줬다.

 

이 문제를 계기로 비트마스크가 어렵지 않다고 느껴졌는데, 어떤 문제에 비트마스크를 적용해야하는지 조금 더 문제를 풀면서 감을 찾아야겠다.

 

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Teaching_1062 {
  static final int ASCII_DEFAULT = 97, ALPHABET_LENGTH = 26;

  static int answer;
  static int[] words;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken()) -5; // prefix, suffix 기본 5개 a c i n t
    words = new int[n];

    for(int i=0; i<n; i++) {
      String inputWord = br.readLine();
      int len = inputWord.length();
      for(int j = 0; j<len; j++) {
        words[i] |= (1 << (inputWord.charAt(j) - ASCII_DEFAULT));
      }
    }

    br.close();
    solution(m);
  }

  private static void solution(int m) {
    if(m>=0) {
      final int[] DEFAULT_ALPHABETS = {0,2,8,13,19}; // a, c, i, n, t
      boolean[] check = initCheck(DEFAULT_ALPHABETS);
      int bitMask = 0;
      for(int idx : DEFAULT_ALPHABETS) {
        bitMask |= (1 << idx);
      }
      permutation(1, m, bitMask, check);
    }
    System.out.println(answer);
  }

  private static boolean[] initCheck(int[] DEFAULT_ALPHABET) {
    boolean[] check = new boolean[ALPHABET_LENGTH];
    for(int idx : DEFAULT_ALPHABET) {
      check[idx] = true;
    }
    return check;
  }

  private static void permutation(int index, int count, int bitMask, boolean[] check) {
    if(count == 0) {
      // 검증
      findMax(bitMask);
      return;
    }
    if(index == ALPHABET_LENGTH) { // out of index
      return;
    }
    if(!check[index]) { // 새로 추가하는 경우
      check[index] = true;
      permutation(index+1, count-1, bitMask | (1 << index), check);
      check[index] = false;
    }
    permutation(index+1, count, bitMask, check); // 추가 없이 다음으로
  }

  private static void findMax(int bitMask) {
    int count =0;
    for(int target : words) {
      if(target == (target & bitMask)) {
        count++;
      }
    }

    answer = Math.max(count, answer);
  }
}