[BOJ 1062] 가르침

 

문제출처

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

1062번: 가르침

 

문제풀이

문자열을 처리하는 문제이다. 문제에서 남극언어는 "anta"로 시작되고 "tica"로 끝난다고 주어졌다. 즉 모든 언어를 읽기 위해서는 "a", "n", "t", "i", "c"는 무조건 배워야 한다는 것이다. 즉 k가 주어졌을때 이 5개는 배웠다 생각하고 처리했다. 주어진 n개의 단어에서 replaceAll 메서드를 활용해 5개 문자를 제외시켰고 문자를 배웠음을 의미하는 visit배열을 true처리해줬다.

이후 dfs를 이용해서 k개의 단어를 배울때까지 모든 방법을 전체 탐색해 k개의 단어를 배웠다면 읽을 수 있는 단어의 갯수를 카운팅해주는 방식으로 풀이했다.

 

지금 생각해보니 visit배열대신 비트마스크를 사용해도 될것같다. 아래글처럼 visit배열대신 비트마스크를 사용할 수 있다. 

 

프로그래머스 64064] - 카카오 불량 사용자

[프로그래머스 64064] - 카카오 불량 사용자

 

 

 

소스코드

https://github.com/sw93/algorithm/blob/master/BOJ_PS/BOJ_1062.java

sw93/algorithm

 

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

public class BOJ1062 {
    private static int n, k, ans;
    private static String[] words = new String[51];
    private static boolean[] visit = new boolean[26];
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;

    private static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            String word = st.nextToken();

            // a n t i c 필수
            word = word.replaceAll("a" , "");
            word = word.replaceAll("n" , "");
            word = word.replaceAll("t" , "");
            word = word.replaceAll("i" , "");
            word = word.replaceAll("c" , "");
            words[i] = word;
        }
        visit['a'-'a'] = true;
        visit['n'-'a'] = true;
        visit['t'-'a'] = true;
        visit['i'-'a'] = true;
        visit['c'-'a'] = true;

    }
    private static void checkString() {
        int count = 0;

        for (int i=0; i<n; i++) {
            boolean isRead = true;
            for (int j=0; j<words[i].length(); j++) {
                if (!visit[words[i].charAt(j) - 'a']) {
                    isRead = false;
                    break;
                }
            }

            if (isRead) {
                count++;
            }
        }
        ans = Math.max(ans, count);
    }

    private static void dfs(int index, int depth) {
        if (depth == k) {
            checkString();
            return;
        }

        for (int i=index; i<26; i++) {
            if (visit[i]) continue;

            visit[i] = true;
            dfs(i, depth+1);
            visit[i] = false;
        }
    }

    public static void main(String[] args) throws Exception {
        init();
        // a n t i c 필수
        if (k < 5) {
            System.out.println(0);
            return;
        } else if (k == 26) {
            System.out.println(n);
            return;
        }
        k -= 5;
        dfs(0, 0);
        System.out.println(ans);
    }
}