백준 9997 자바 - 폰트 (BOJ 9997 JAVA)

문제 : boj9997

 

 

  1,2,3에 걸쳐서 점점 효율성이 좋은 풀이를 설명할 겁니다. 그러니 최종적으로는 '3'만 보셔도 되긴합니다. 왜 그렇게 설명하냐면 제가 그렇게 풀었기 때문입니다 ㅋㅋㅋ 시간 제한 딱 맞춰서 푸는건(1초제한인데 백준에서 자바로 제출할 시 '원래시간*2+1'초 이므로 자바로는 3초제한 이었어요.) 뭔가 기분나빠서 줄이다보니 줄여지네요.

 

 

1. 우선 빠듯하게 가능한 풀이

  우선 모든 경우를 살펴보는게 가능할지 생각해보면, O(2^25*100*26)가 필요하다(2는 해당 문자를 사용하거나, 안하거나이고 25는 N의 최대수치, 100은 단어 길이의 최대수치, 26은 a~z 모든 문자가 포함되었는지 확인). 상당히 빠듯하긴 하지만, 어찌보면 할만해 보이므로 일단 해봤다. 이 때 단어 길이는 100이지만, 어차피 포함된 문자는 'a'~'z'로 26개이므로 전처리를 한다면 O(2^25*26*26)으로 줄일 수 있다. 모든 경우를 살펴본다함은 예를들어 '예제 입력 2'에 대해 다음과 같이 모든 경우를 보겠다는 말이다.

 

  추가로 모든 문자가 포함되었는지 포함하는 부분도 시간을 줄여서 O(2^25*26)으로 가능하다. cnt라는 변수를 둬서 현재 a~z중 존재하는 문자의 수를 세고, arr[26]을 둬서 이걸로 현재까지 나온 a~z 각각의 개수를 센다고 해보자. 이 경우 예를들어 'a'라는 문자가 나왔다면 arr[0]++; 를 하면 될 것이고, 'z'라는 문자가 빠진다면 arr[25]--; 를 하면 될 것이다. 또한 arr의 특정 문자에 해당하는 카운팅이 증거하거나 감소할 때, 증가했는데 1이 됬다면 cnt++;, 감소했는데 0이 됬다면 cnt--;를 한다면, 매번 a~z가 모두 존재하는지에 대한 확인은 cnt==26 인지만 보면 되므로 O(1)로 가능해져서, O(2^25*26)까지 줄일 수 있다.

 

  이렇게 짠 코드는 다음과 같다. 이 경우 2724ms가 나왔다.

[ 코드 1 - 브루트포스 ]

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

public class Main {
    int n, ans;
    ArrayList<Integer>[] exist;
    int[] arr = new int['z'-'a'+1];
    int cnt = 0;

    private void add(int c) { if (++arr[c] == 1) cnt++; }
    private void remove(int c) { if (--arr[c] == 0) cnt--; }

    private void proc(int idx) {
        if (idx == n) return;

        for (int i = 0; i < exist[idx].size(); i++) add(exist[idx].get(i));
        if (cnt==26) ans++;
        proc(idx+1);

        for (int i = 0; i < exist[idx].size(); i++) remove(exist[idx].get(i));
        proc(idx+1);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        exist = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            exist[i] = new ArrayList<>();
            HashSet<Integer> hs = new HashSet<>();
            String cur = br.readLine();
            for (int j = 0; j < cur.length(); j++) {
                int atoi = cur.charAt(j)-'a';
                if (!hs.contains(atoi)) {
                    hs.add(atoi);
                    exist[i].add(atoi);
                }
            }
        }
        proc(0);
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

 

2. 좀 더 시간을 줄여보자!

  '1'은 단순 브루트포스로 해봤다. 근데, 잘 생각해보면 이미 cnt가 26인 시점에서, 그 이후로는 문자를 추가하던 추가하지 않던 확인할 것도 없이 a~z가 모두 존재한다. 예를들어 다음과 같이 주어졌을 경우를 봐보자.

3
abcdefghijklmnopqrstuvwxyz
abcde
z

이 경우 이미 0번에서 a~z가 모두 나왔다. 따라서 0번을 사용했다면 굳이 그 뒤를 진행하지 않아도 문제가 없다. 그럼 중간에 멈췄을 때, 그 뒤에 몇개의 경우가 있는지만 알면 해당 위치에서 더 보지않고 끝낼 수 있다. 몇개인지는 '2^(N - 현재 보고있는 인덱스 위치)'가 될 것이다. 코드에서는 이걸 비트연산으로 'ans += 1<<(n-idx);' 로 나타냈다.

  이렇게 짠 코드는 다음과 같다. 712ms가 나왔다.

[ 코드 2 - 브루트포스 + 백트래킹 ]

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

public class Main {
    int n, ans, cnt;
    ArrayList<Integer>[] exist;
    int[] arr = new int['z'-'a'+1];

    private void add(int c) { if (++arr[c] == 1) cnt++; }
    private void remove(int c) { if (--arr[c] == 0) cnt--; }

    private void proc(int idx) {
        if (cnt==26) {
            ans += 1<<(n-idx);
            return;
        }
        if (idx == n) return;

        for (int i = 0; i < exist[idx].size(); i++) add(exist[idx].get(i));
        proc(idx+1);

        for (int i = 0; i < exist[idx].size(); i++) remove(exist[idx].get(i));
        proc(idx+1);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        exist = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            exist[i] = new ArrayList<>();
            HashSet<Integer> hs = new HashSet<>();
            String cur = br.readLine();
            for (int j = 0; j < cur.length(); j++) {
                int atoi = cur.charAt(j)-'a';
                if (!hs.contains(atoi)) {
                    hs.add(atoi);
                    exist[i].add(atoi);
                }
            }
        }
        proc(0);
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}​

 

 

 

3. 한번 더 줄여보자!

  사실 a~z에 대한 체크를 굳이 arr[26]과 같이 배열로 할 필요가 없다. int형은 26개 이상의 비트를 가지고 있으므로, 비트를 통해 체크할 수 있다. 그럼 arr[26]이 int 하나로 줄어드는 것이다(예를들어 b,d가 존재했다면 0x00..001010과 같이 1<<1과 1<<3을 체크한다.). 그럼 이제 cnt와 arr이 필요없고, 현재 더한 값이 비트 단위로 1이 우측부터 26개 모두 켜져있는 0x00..11111...11 (1이 26개)인지 확인하면 될 것이다. 이 경우 O(2^25*26)에서 O(2^25)로 줄일 수 있다. 백트래킹 부분은 테스트 케이스에 따라 영향도가 달라지므로 따로 시간복잡도에 포함시키지 않았다.

 

  코드에서 GOAL = (1<<26)-1; 은 GOAL = 0x00..1111..11 (1이 26개)와 동일한 의미이다. 비트연산으로 하기 싫다면 뭐 Integer.parseInt("1111...11", 2); (1이 26개인 문자) 이렇게 해도 된다. 참고로 a |= 1<<b; 는 a의 값 중 우측부터 b번째 비트를 1로 놓는 것이다. 이미 1이라면 무시되므로 문자의 길이가 100개라도 어쨌든 우측부터 26개까지의 비트에만 영향을 끼친다.

 

  이렇게 짠 코드는 다음과 같고, 최종적으로 2724ms에서 204ms로 줄어들게 되었다.

[ 최종 코드 - 브루트포스 + 백트래킹 + 비트마스킹 ] : github

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

public class Main {
    private static final int GOAL = (1<<26)-1;
    int n, ans, tmp;
    int[] exist;

    private void proc(int idx) {
        if (tmp == GOAL) {
            ans += 1<<(n-idx);
            return;
        }
        if (idx == n) return;
        int tmpMem = tmp;

        tmp |= exist[idx];
        proc(idx+1);

        tmp = tmpMem;
        proc(idx+1);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        exist = new int[n];
        for (int i = 0; i < n; i++) {
            HashSet<Integer> hs = new HashSet<>();
            String cur = br.readLine();
            for (int j = 0; j < cur.length(); j++) {
                int atoi = cur.charAt(j)-'a';
                if (!hs.contains(atoi)) {
                    hs.add(atoi);
                    exist[i] |= 1<<atoi;
                }
            }
        }
        proc(0);
        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}