[JAVA] BOJ 백준 1062번 - 가르침

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

1062번: 가르침

---

2. 내가 푼 방법

읽을 수 있는 단어의 최대 값을 구해야 하기 때문에, 완전탐색을 이용했다.

 

먼저 처음에 입력을 받을 때 시작 글자 "anti"와 끝 글자 "tica"를 replaceAll로 없앴기 때문에, 완전 탐색이 이뤄질 필요가 없는 케이스들을 바로 리턴해주었다.

for (int i = 0; i < N; i++) {
    arr[i] = br.readLine().replaceAll("anta", "").replaceAll("tica", "");
}

 

그래서 K가 5보다 작은 경우에는 기본 시작과 끝 글자를 가르칠 수 없기 때문에 항상 0이 되고, K가 26일 경우에는 모든 글자를 가르칠 수 있기 때문에 항상 N이 된다.

public static void solution() {
    if (K < 5) {
        return;
    }
    if (K == 26) {
        result = N;
        return;
    }

    boolean[] learn = new boolean['z' - 'a' + 1];
    learn['a' - 'a'] = true;
    learn['n' - 'a'] = true;
    learn['t' - 'a'] = true;
    learn['i' - 'a'] = true;
    learn['c' - 'a'] = true;

    choice(learn, 0, 5);
}

 

 

이제 모든 케이스들을 탐색해준다. 이때 탐색을 빠져나올 base condition을 잘 설정하는 것이 중요하다.

따라서 alphaIdx 값이 26을 넘어갈 경우, 배운 글자인 cnt 값이 K를 넘어갈 경우에 탐색을 마친다.

(위에 solution 함수를 보면 cnt 값은 5부터 시작하는 것을 주의하자)

public static void choice(boolean[] learn, int alphaIdx, int cnt) {
    if (alphaIdx == 'z' - 'a' + 1 || cnt >= K) {
        result = Math.max(result, getCanLearn(learn));
        return;
    }

    choice(learn, alphaIdx+1, cnt);

    if (!learn[alphaIdx]) {
        learn[alphaIdx] = true;
        choice(learn, alphaIdx+1, cnt+1);
        learn[alphaIdx] = false;
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B1062.java

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

class Main {
    static int N;
    static int K;
    static String[] arr;
    static int result;

    public static void main (String[] args) throws IOException {
        init();
        solution();
        print();
    }

    public static void solution() {
        if (K < 5) {
            return;
        }
        if (K == 26) {
            result = N;
            return;
        }

        boolean[] learn = new boolean['z' - 'a' + 1];
        learn['a' - 'a'] = true;
        learn['n' - 'a'] = true;
        learn['t' - 'a'] = true;
        learn['i' - 'a'] = true;
        learn['c' - 'a'] = true;

        choice(learn, 0, 5);
    }

    public static void choice(boolean[] learn, int alphaIdx, int cnt) {
        if (alphaIdx == 'z' - 'a' + 1 || cnt >= K) {
            result = Math.max(result, getCanLearn(learn));
            return;
        }

        choice(learn, alphaIdx+1, cnt);

        if (!learn[alphaIdx]) {
            learn[alphaIdx] = true;
            choice(learn, alphaIdx+1, cnt+1);
            learn[alphaIdx] = false;
        }
    }

    public static int getCanLearn(boolean[] learn) {
        int cnt = 0;

        for (int i = 0; i < N; i++) {
            String str = arr[i];

            boolean canLearn = true;
            for (int j = 0; j < str.length(); j++) {
                if (!learn[str.charAt(j) - 'a']) {
                    canLearn = false;
                    break;
                }
            }

            if (canLearn) cnt++;
        }

        return cnt;
    }

    public static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void init() 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());
        arr = new String[N];

        for (int i = 0; i < N; i++) {
            arr[i] = br.readLine().replaceAll("anta", "").replaceAll("tica", "");
        }

        br.close();
    }
}

---

4. 결과 및 회고

완전탐색의 경우에는 탐색을 빠져나오는 base condition이 중요한 것 같다.