백준 - 가르침

문제 링크 ▶︎ 가르침

문제 파악

이 문제는 알파벳 중에서 어떤 k개만을 선택했을 때 최고의 선택이 되는지를 구하는 문제이기 때문에 백트래킹으로 풀려고 생각했다.
시간을 조금이라도 줄이기 위해서 전체 알파벳이 아닌 문제에서 주는 알파벳을 가지고 백트래킹을 돌리면서 최선의 선택을 구하면 된다.
그리고 'a', 'c', 'i', 'n', 't'는 없으면 답이 0이기 때문에 선제적으로 조건 처리를 해주면 좋다.

접근 방법

1. k<5 라는 것은 'a', 'c', 'i', 'n', 't'를 표현못하는 것이기 때문에 답은 0이 된다는 것을 먼저 처리해준다.

2. 해시셋을 이용해서 알파벳 후보군과 들고있는 k개의 알파벳을 모두 관리하는데, loop 함수는 주어진 k개의 알파벳으로 최대 몇개의 단어를 표현할 수 있는지 정답을 구하는 함수이고, setting 함수는 주어진 단어들에 대한 알파벳 후보군을 해시셋에 저장하는 함수다.

3. setting 함수부터 자세히 본다면 필수로 존재해야하는 'a', 'c', 'i', 'n', 't'을 제외하고서 주어진 단어에서 어떤 알파벳이 존재하는 지에 대한 정보를 charList 해시셋에 추가한다.

4. loop 함수를 보면 단순하게 주어진 스트링 배열을 전부 순회하면서 k개의 알파벳이 담긴 set에 포함되어있는지 아닌지로 최대 정답을 리턴한다.

5. 백트래킹 처리를 하는 bt함수를 보면 해시셋의 크기가 k개가 되거나 k개가 되지않아도 스트링 배열에 나온 알파벳을 모두 처리했다면 loop함수를 통해서 정답을 리턴하고, 그게 아니라면 temp라는 변수를 사용해서 알파벳 후보군 리스트에서 인덱스에 순차적으로 접근하면서 해시셋에 넣었다가 빼면서 백트래킹 처리를 해준다. 여기에서 temp 처리(즉, 방문 처리)를 하지 않으면 조합이 아닌 순열 개념으로 처리되니까 시간적으로 손해를 볼 수 있다.

코드 구현

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

public class Main {
    public static int answer;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        String[] strList = new String[n];
        Set<Character> charList = new HashSet<>();

        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            strList[i] = str;
        }
        if (k < 5) {
            System.out.println(0);
        } else {
            Set<Character> set = new HashSet<Character>();
            insert(set);
            answer = loop(set, strList);
            setting(set, strList, charList);
            List<Character> list = new ArrayList<>(charList);
            bt(k, set, list, strList, 0);
            System.out.println(answer);
        }
    }
    public static void bt(int k, Set<Character> set, List<Character> list, String[] strList, int temp) {
        if (set.size() == k || set.size() == (list.size() + 5)) {
            answer = Math.max(answer, loop(set, strList));
            return ;
        }
        for (int i = temp; i < list.size(); i++) {
            if (!set.contains(list.get(i))) {
                set.add(list.get(i));
                bt(k, set, list, strList, i+1);
                set.remove(list.get(i));
            }
        }
    }
    public static void setting(Set<Character> set, String[] strList, Set<Character> charList) {
        for (String str : strList) {
            for (int i = 0; i < str.length(); i++) {
                if (!set.contains(str.charAt(i)) && !charList.contains(str.charAt(i))) {
                    charList.add(str.charAt(i));
                }
            }
        }
    }
    public static void insert(Set<Character> set) {
        set.add('a');
        set.add('c');
        set.add('i');
        set.add('n');
        set.add('t');
    }
    public static int loop(Set<Character> set, String[] strList) {
        int cnt = 0;
        for (String str : strList) {
            boolean flag = true;
            for (int i = 0; i < str.length(); i++) {
                if (!set.contains(str.charAt(i))) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                cnt++;
            }
        }
        return cnt;
    }
}

개선 사항

풀고자 하는 개념은 있었지만 구현을 너무 엉망으로 한듯하다.
그리고 각 스트링에 대해서 anta, tica를 자르고 봤어도 괜찮았을 것 같다.