1062번 - 백트래킹

이번 문제는 혼자 풀지 못한 문제이다.

K종류의 알파뱃만 사용 가능할 시 anta로 시작하고 tica로 끝나는 단어 N 개중 몇 단어를 완성시킬 수 있는지에 대한 문제였다.
처음에는 a n t i c가 담긴 hashset에 재귀를 이용해 각 단어의 글자를 추가하여, 몇 단어가 최대인지 맞추려고 했다.

하지만 시간초과가 나왔다. 틀린 풀이는 아래와 같다.

package wrong;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

public class 가르침_1062번_틀림 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        sc.nextLine();
        if (K < 5) {
        System.out.println(0);
            System.exit(0);
        } else if (K == 26) {
        System.out.println(N);
            System.exit(0);
        }

        Set<Character> hashset = new HashSet<>();
        hashset.add('a');
        hashset.add('n');
        hashset.add('t');
        hashset.add('i');
        hashset.add('c');

        String[] words = new String[N];
        for (int i = 0; i < N; i++) {
            String input = sc.nextLine();
            words[i] = input.substring(4, input.length()-4);
        }

        AtomicInteger max = new AtomicInteger(0);
        recursion(hashset, N, K-5, words, 0, 0, max);
        System.out.println(max);
    }

    static void recursion(Set<Character> hashset, int N, int K, String words[], int count, int num,  AtomicInteger max) {
        for (int i = count; i < N; i++) {
            Set<Character> copySet = new HashSet<>(hashset);
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                copySet.add(word.charAt(j));
            }
            int size = copySet.size() - hashset.size();
            if (size <= K) {
                recursion(copySet, N, K-size, words, i+1, num+1, max);
            }
        }
        max.set(Math.max(max.get(), num));
    }
}

이후 오랜시간 고민해 보았지만, 풀이법이 생각나지 않아 다음 블로그를 참고했다.

[백준]1062: 가르침 - JAVA :: 빈둥벤둥 IT logging (tistory.com)

[백준]1062: 가르침 - JAVA

이 블로그에서는 단어를 기준으로 한게 아닌 알파벳을 기준으로 잡았다.

단어 개수가 적을 때, 단어를 기준으로 하는 방법이 더 빠르겠지만, 만일 단어의 수가 많아지면, 단어를 기준으로 하는 것은 매우 비효율적인 방법이 될 것이다.

그렇게 위 블로그를 참고하여 다음 코드를 작성하였다.

import java.util.Scanner;

public class 가르침_1062번 {
    static int N,K;
    static String[] words;
    static boolean[] alphabet;
    static int max = 0;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        K = sc.nextInt();
        sc.nextLine();
        
        if (K < 5) {
            System.out.println(0);
            System.exit(0);
        } else if (K == 26) {
            System.out.println(N);
            System.exit(0);
        }

        words = new String[N];
        alphabet = new boolean[26];

        alphabet['a' - 'a'] = true;
        alphabet['n' - 'a'] = true;
        alphabet['t' - 'a'] = true;
        alphabet['i' - 'a'] = true;
        alphabet['c' - 'a'] = true;

        for (int i = 0; i < N; i++) {
            String input = sc.nextLine();
            words[i] = input.substring(4, input.length()-4);
        }
        backTracking(0, 0);

        System.out.println(max);
    }

    static void backTracking(int alpha, int count) {
        if (count == K - 5) {
            int num = 0;
            for (int i = 0; i < N; i++) {
                boolean noCost = true;
                for (int j = 0; j < words[i].length(); j++) {
                    if (!alphabet[words[i].charAt(j) - 'a']) {
                        noCost = false;
                        break;
                    }
                }
                if (noCost) {
                    num ++;
                }
            }
            max = Math.max(max, num);
        }
        for (int i = alpha; i < 26; i++) {
            if (!alphabet[i]) {
                alphabet[i] = true;
                backTracking(i, count+1);
                alphabet[i] = false;
            }
        }
    }
}

너무 문제에 대한 시야가 좁았던 것이 문제를 일으킨 것 같다.

위 블로그를 참고하며, 내가 전역변수를 사용하지 않고 있었다는 것을 알게되었다.

javaScript를 사용한 프론트엔드 개발시 그렇게 많이 사용을 했었는데.... 스프링을 이용한 백엔드 개발시 Service 코드 작성시 전역변수를 잘 이용하지 않았다는 점에서 영향을 받고 있었던 것 같다.

전역변수를 사용해 더욱 깔끔한 알고리즘 풀이를 지향해야겠다.