[BOJ] 1062 가르침 (Java)

1. 문제 링크

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

1062번: 가르침

 

2. 접근법

알파벳은 26 글자이므로 2^26으로 선택한 k개의 글자들을 표현할 수 있다.

ex)

a == 1

b == 10

z == 10000000000000000000000000

a, b, z를 선택했다면 == 10000000000000000000000011

 

이렇게 선택한 글자들을 비트 마스크로 표현하고,

입력받은 각 단어 또한 글자 중복을 제거하여 비트 마스크로 표현한다.

두 비트 마스크를 AND 연산하여 해당 글자를 만들 수 있는지 판단한다.

 

1. 입력 단어들을 비트 마스크로 변환해서 int[] words에 담기

1.1. convertWordToBitMask() 함수 사용

1.2. 입력 단어의 각 글자 ch를 자릿수에 맞게 표현해서 result에 담기

for(char ch : chars) {
result = result | (1 << (ch - 'a'));
}

2. 예외 처리

2.1. k < 5 라면 a, n, t, i, c 글자를 아예 만들 수 없으므로, 만들 수 있는 단어가 없음. reutrn 0

2.2. k == 26이라면, 모든 알파벳을 만들 수 있으므로, 입력 받은 모든 단어를 만들 수 있음. reutrn n

 

3. boolean[] visited에 각 글자를 선택했는지 여부를 담기

3.1. a, n, t, i, c는 무조건 선택해야 함

 

4. backTracking()을 통해 글자를 조합해서 visited[]에 담기

 

5. 총 k개의 글자를 선택했다면, 읽을 수 있는 단어 개수 구하기. searchReadableWords() 함수 사용

5.2. visited[]를 기반으로 선택된 글자라면 index만큼 자릿수를 맞추어 result에 담기

        for(int i = 0; i < 26; i++) {
            if(visited[i]) {
                result = result | (1 << i);
            }
        }

5.3. result를 readableBitMask에 담아 words[i]의 각 글자와 비교하기

        // visited[]를 기반으로 읽을 수 있는 글자 배열을 비트 마스크로 변환하기
        int readableBitMask = convertVisitedToBitMask();

        int cnt = 0;
        for(int i = 0; i < n; i++) {
            // words[i]의 글자가 readableBitMask에 모두 포함되었는지 구분하기
            if((readableBitMask & words[i]) == words[i]) cnt++;
        }

        ans = Integer.max(ans, cnt);

5.3.1. readableBitMask에 words[i]의 모든 글자가 포함되었다면, AND 연산을 해면 words[i]가 나와야 함

 

3. 코드

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

// 가르침

public class BJ1062 {

    static int n, k;
    static int ans;
    static int[] words;
    static boolean[] visited = new boolean[26];
    
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        // 입력 단어들을 비트 마스크로 변환해서 words[]에 담기
        words = new int[n];
        for(int i = 0; i < n; i++) {
            String input = br.readLine();
            words[i] = convertWordToBitMask(input);
        }

        if(k < 5) {
            ans = 0;
        }
        else if(k == 26) {
            ans = n;
        }
        else {
            // visited[]에 a, n, t, i, c 저장하기
            visited['a' - 'a'] = true;
            visited['n' - 'a'] = true;
            visited['t' - 'a'] = true;
            visited['i' - 'a'] = true;
            visited['c' - 'a'] = true;
                
            backTracking(0, 0);        
        }

        System.out.println(ans);
    }

    private static int convertWordToBitMask(String input) {

        char[] chars = input.toCharArray();
        int result = 0;
        
        for(char ch : chars) {
            result = result | (1 << (ch - 'a'));
        }

        return result;
    }

    private static void backTracking(int depth, int start) {

        if(depth == k - 5) {
            // 만들어진 글자 조합으로 읽을 수 있는 단어 개수 구하기
            searchReadableWords();
            return;
        }

        // k - 5 개로 이루어진 조합을 찾아 visited[]에 저장하기
        for(int i = start; i < 26; i++) {
            if(visited[i]) continue;

            visited[i] = true;
            backTracking(depth + 1, i + 1);
            visited[i] = false;
        }
    }

    private static void searchReadableWords() {

        // visited[]를 기반으로 읽을 수 있는 글자 배열을 비트 마스크로 변환하기
        int readableBitMask = convertVisitedToBitMask();

        int cnt = 0;
        for(int i = 0; i < n; i++) {
            // words[i]의 글자가 readableBitMask에 모두 포함되었는지 구분하기
            if((readableBitMask & words[i]) == words[i]) cnt++;
        }

        ans = Integer.max(ans, cnt);
    }

    private static int convertVisitedToBitMask() {

        int result = 0;
        
        for(int i = 0; i < 26; i++) {
            if(visited[i]) {
                result = result | (1 << i);
            }
        }

        return result;
    }
}

 

4. 막힌 부분

며칠 전 코테에서 Bit Mask 문제가 나왔는데 제대로 풀지 못했다..

보완하고자 Bit Mask 유형의 문제를 찾은 후 풀기 시작했다.

근데 이게 왜 Bit Mask 유형이죠..? (다른 방법으로도 풀 수 있는 문제긴 했음)

 

다른 분들의 풀이를 참고하니 그제야 보였다.

아직까진 코테에서 활용하긴 조금 힘들 듯 하다.

몇 문제 더 연습해야겠다.