[백준 *Java] - 가르침(1062)

가르침

1062번: 가르침

문제

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

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

입력

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

---

👇 접근방식

남극언어의 모든 단어는  "anta", "tica" 로 시작되고, 끝이납니다.
이 말은, "a, c, i, n ,t" 라는 알파벳은 무조건 단어에 포함 되어있어야 합니다.

로직 flow 정리
1. 입력 받은 단어 중에 "a, c, i, n ,t" 이 없다면 return 0.
2. 가르칠 수 있는 수가 5개 미만일 경우, return 0.
3. 가르칠 수 있는 수가 많아, 입력 받은 단어를 다 만들 수 있다면? return N.
4. 그게 아닐 시? 조합을 이용하여 최소 알파벳("a, c, i, n ,t")을 제외한 알파벳을 뽑아 조합을 만들기
5. 조합을 만들 땐, 방문 처리를 이용하여 true / false 로 조합로 만듭니다. (즉, true 는 조합된 알파벳)
6. 조합이 만들어 졌다면 조합된 알파벳을 가지고 단어를 몇 개 만들 수 있는지 확인하기
7. 위 로직을 거쳐, 학생들이 읽을 수 있는 단어의 최댓값(Math.max)을 구하기

 

아래는 성공한 코드입니다. 로직에 주석을 달아 놓았습니다.

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

public class Main {
    static int N, K;
    static boolean[] visited = new boolean[26];
    static HashSet<Character> hs = new HashSet<>();
    static ArrayList<Character> al = new ArrayList<>();
    static int max = Integer.MIN_VALUE;
    static String[] line;

    /* dfs 함수 로직
        가르칠 수 있는 수를 가지고 방문처리를(true / false)로 알파벳 조합을 만듭니다.
        조합은 visited 방문처리 ture 된 것이 사용가능한 조합이라 생각합니다.
     */
    private static void dfs(int start, int depth) {
        if (depth == K - 5) {
            isEligibilityCheck();
            return;
        }

        for (int i = start; i < al.size(); i++) {
            char c = al.get(i);
            visited[c - 'a'] = true;
            dfs(i + 1, depth + 1);
            visited[c - 'a'] = false;
        }
    }

    /* isEligibilityCheck 함수 로직
        dfs 에서 조합한 알파벳을 가지고, 입력 받은 단어 중에 사용 가능한 단어가 몇 개 있는 지 확인을 합니다.
     */
    private static void isEligibilityCheck() {
        int count = 0;
        
        for (int i = 0; i < N; i++) {
            boolean flag = true;
            for (int j = 0; j < line[i].length(); j++) {
                char c = line[i].charAt(j);
                if (!visited[c - 'a']) {
                    flag = false;
                    break;
                }
            }
            if (flag) count++;
        }
        max = Math.max(max, count);
    }

    // 이 메서드 역할은 최소 필요한 알파벳 "a, c, i, n ,t" 의 갯수 조차 안될 시, false
    // 또한, 아까 HashSet 에 빼면서 최소로 필요한 알파벳("a, c, i, n ,t" )이 방문 처리가 안됐을 시, 애당초 단어를 못 만듭니다. 그러니 false
    private static boolean init() {
        if (K < 5) return false;
        if (!(visited['a' - 'a'] && visited['c' - 'a'] && visited['i' - 'a'] && visited['n' - 'a'] && visited['t' - 'a'])) {
            return false;
        }
        return true;
    }

    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());
        line = new String[N];

        /* for 문 내에 for 문 로직
            이 과정에선 HashSet 자료구조를 이용하여, 총 단어의 알파벳이 중복을 피하고, 어떤 종류의 알파벳이 있는지 구별하기 위함입니다.
         */
        for (int i = 0; i < N; i++) {
            line[i] = br.readLine();
            for (int j = 0; j < line[i].length(); j++) {
                hs.add(line[i].charAt(j));
            }
        }
        /* for 문 내에 if 문 로직
            총 단어의 알파벳을 하나씩 뽑아서, 꼭 들어있어야하는 조건 "a, c, i, n ,t" 알파벳이 있다면, 방문처리 true 처리 합니다.
         */
        for (char c : hs) {
            if (c == 'a' || c == 'c' || c == 't' || c == 'i' || c == 'n') {
                visited[c - 'a'] = true;
            // "a, c, i, n ,t" 제외하곤, list 에 담아 놓습니다.
            }else al.add(c);
        }

       /* if 로직
            최소한의 기본 세팅이 안됐을 시, 0을 return
        */
        if (!init()) {
            System.out.println(0);
            return;
        }

        /* if else 로직.
             위 과정을 다 처리한 뒤에선, 최소 알파벳인 "a, c, i, n ,t" 이 존재할 것이며,
             al 이라는 ArrayList 에 최소 알파벳을 제외한 알파벳이 담겨져 있을 것입니다.
         */

        if (K-5 >= al.size()) max = N; // 만약 조합해야 할 알파벳 보다, 가르칠 수 있는 알파벳이 많다면? 그냥 모든 단어를 사용할 수 있다.
        else dfs(0, 0); // 그게 아닐 시, dfs 로 조합 시작
        System.out.println(max);

    }
}

 

후기

이번 문제에서 느꼈던 건 사용여부 확인이 필요할 땐 visited를 이용하여 사용여부를  true / false 처리를 하여 BackTracking 을 해준다고 어느정도 정형화 시킬 수 있다는 생각이 들었습니다.

다양하게 풀었던 BackTracking 문제가 점차 정리가 되어가고있는 거 같습니다.