[BOJ] 1062 가르침 - JAVA

1. 문제

1062번: 가르침

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

---

2. 풀이

Main

단어를 비트마스킹을 이용해 int로 나타낸다.

만약 입력받은 K가 5보다 작다면 필수단어를 포함시키지 못하므로 바로 0을 출력하고 끝낸다.

알파벳 뽑는 메서드를 호출한다. 이 때, flag값은 a,n,t,i,a를 포함한 값으로 한다. cnt값은 5부터 시작한다.

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   K = Integer.parseInt(st.nextToken());

   words = new int[N];
   for(int i=0;i<N;i++){
      for(char ch:in.readLine().toCharArray()){
         words[i]|=1<<ch-'a';
      }
   }

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

   //a n t i c
   pick(5,0,1|(1<<'n'-'a')|(1<<'t'-'a')|(1<<'i'-'a')|(1<<'c'-'a'));
   System.out.println(ANSWER);
}

 

Pick

알파벳을 K개만큼 뽑는 메서드다. 

이미 뽑았다면 넘어가고, 안뽑았다면 다음 알파벳을 재귀호출한다.

cnt==K만큼 뽑았을 때 단어개수를 체크하는 메서드를 호출한다.

public static void pick(int cnt, int start, int flag){
   if(cnt==K){
      check(flag);
      return;
   }

   for(int i=start;i<26;i++){
      if((flag&1<<i)!=0) continue;
      pick(cnt+1,i+1,flag|1<<i);
   }
}

 

Check

배울 수 있는 단어 개수를 세는 메서드다.

뽑힌 알파벳들(flag)와 i번째 단어를 |해서 합친 뒤, flag만 ^연산으로 제거한다. 이 값이 0이라면 가능한 단어이므로 count+1한다.

모든 단어를 다 체크했다면 ANSWER과 count를 비교해 큰 값을 ANSWER에 저장한다.

public static void check(int flag){
   int count = 0;
   for(int i=0;i<N;i++){
      if(((flag|words[i])^flag) == 0) count++;
   }

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

 

전체 코드

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

public class BOJ_1062_가르침 {
   static int ANSWER = 0;
   static int[] words;
   static int N,K;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());

      words = new int[N];
      for(int i=0;i<N;i++){
         for(char ch:in.readLine().toCharArray()){
            words[i]|=1<<ch-'a';
         }
      }

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

      //a n t i c
      pick(5,0,1|(1<<'n'-'a')|(1<<'t'-'a')|(1<<'i'-'a')|(1<<'c'-'a'));
      System.out.println(ANSWER);
   }

   public static void pick(int cnt, int start, int flag){
      if(cnt==K){
         check(flag);
         return;
      }

      for(int i=start;i<26;i++){
         if((flag&1<<i)!=0) continue;
         pick(cnt+1,i+1,flag|1<<i);
      }
   }

   public static void check(int flag){
      int count = 0;
      for(int i=0;i<N;i++){
         if(((flag|words[i])^flag) == 0) count++;
      }

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

---

3. 결과

1) 단어리스트 기준으로 재귀호출하며 반복했더니 시간초과났다.

2) 단어를 int로 만들지 않고 하나씩 비교했더니 너무 오래걸렸다. (868ms)

3) 단어도 비트마스킹해서 int로 만들고, or과 xor연산을 이용하니 시간이 훨씬 줄어들었다.(164ms)