[자바] 백준 1342 - 행운의 문자열 (java)

목차

문제 : boj1342

 

 

필요 알고리즘

• 수학 (순열 개념) 또는 브루트포스 + 백트래킹
  
  • 순열 개념을 사용해서 풀 수도 있고, 백트래킹을 써서 풀 수도 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  우선 순열 개념으로 푸는건 뒤로 미루고 브루트포스+백트래킹으로 푸는 것 부터 살펴보자.

단순히 생각해보면 dfs로 모든 경우를 백트래킹하면서 찾은 후, 이미 나온 문자가 아니라면 카운팅하는 방법이 있을 것이다. 대강 O(10! x 중복체크시간복잡도) 정도가 필요하겠지만, 시간적으론 충분히 통과 가능한 시간이다. 문제는 문자열을 최대 10!개 담아두고 비교해야 하므로 이 부분에서 메모리초과가 발생하게 된다.

 

  그래서 다른사람들이 많이 사용한 방법이 각 알파벳을 미리 카운팅해두고 차례대로 사용하는 방식이다. 이 경우 별도로 중복체크를 안해도 되므로 효율적이다. 문제는 내가 이 문제를 dfs로 푸는 것과 관련된 질문을 받아 풀어보게된 점이다. 이 때 이미 다른 사람들이 알파벳을 카운팅해서 풀었고, 차이를 물어보는 질문을 들어버렸다. 그래서 어떻게든 다른 방법으로 풀고싶어졌다(?). 기왕 이렇게된거 질문받은 dfs(완전탐색)로 풀고싶어졌다.

 

  결론은 dfs로 중복체크를 하면서 푸는데 성공했는데, 메모리초과를 해결하기 위한 내 아이디어는 이러하다.

- String으로 중복체크하면 메모리초과난다.

- 그래서 비트마스킹이나 int 같은걸로 가능한 방법을 생각해봤다. 비트마스킹으론 String보다 작게 나오게 하기 힘들어보였다. 정수로 생각해봤는데 어쨌든 'a'부터 'z'까지 표현하려면 한 문자당 2자리수가 필요하므로, 총 20자리가 필요하다. long으로도 안된다 ㅠ

- 근데 문자길이가 최대 10이므로, 서로 다른 문자는 최대 10개가 나온다.

- 따라서 서로 다른 문자를 0부터 9까지 최대 10개에 매핑시키면 한자리수로 표현 가능하고, 총 10자리 정수로 가능하니 long으로 중복체크가 가능해진다.

 

  이렇게 나온게 비효율적이긴 하지만 자존심(이미 들은 방법으로 안풀겠다는)은 챙긴 brute force 버전 코드이다. 아래처럼 cur이라는 long을 하나 두고, 서로 다른 문자열을 0~9의 한 자리 숫자와 매칭해둔 ctoi 배열을 사용해 각 1자리 숫자로 변경해 long으로 중복체크하는 방식이다.

for (int i = 0; i < s.length(); i++) {
    if (v[i] || s.charAt(i) == bf) continue;

    v[i] = true;
    cur *= 10;
    cur += compression[ctoi(s.charAt(i))];
    dfs(idx+1, cur, s.charAt(i));
    cur /= 10;
    v[i] = false;
}

 

---

 

  근데 알파벳 카운팅해서 푸는 방식에 비해 당연히 비효율적이다. 그래서 또 다른 방법으로도 풀어봤는데, c++의 stl에서 제공하는 개쩌는 next_permutation 함수를 자바에 구현해 푸는 방식이다. 그게 이하 코드 중 next permutation 버전 코드이다. 시간 및 메모리는 당연히 엄청나게 차이난다 ㅋㅋ

 

 

코드 (brute force 버전) : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

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

    String s;
    boolean[] v;
    Set<Long> dupChk = new HashSet<>();
    int answer = 0;
    int[] compression;

    private void solution() throws Exception {
        s = br.readLine();
        v = new boolean[s.length()];
        initCompression();

        dfs(0, 1, '-');

        System.out.println(answer);
    }

    private void initCompression() {
        compression = new int['z'-'a'+1];

        Arrays.fill(compression,-1);
        for (int i = 0; i < s.length(); i++) compression[s.charAt(i)-'a']++;
        int comp = 0;
        for (int i = 0; i < compression.length; i++) {
            if (compression[i] != -1)
                compression[i] = comp++;
        }
    }

    private void dfs(final int idx, long cur, char bf) {
        if (idx == s.length()) {
            if (!dupChk.contains(cur)) {
                answer++;
                dupChk.add(cur);
            }

            return;
        }

        for (int i = 0; i < s.length(); i++) {
            if (v[i] || s.charAt(i) == bf) continue;

            v[i] = true;
            cur *= 10;
            cur += compression[ctoi(s.charAt(i))];
            dfs(idx+1, cur, s.charAt(i));
            cur /= 10;
            v[i] = false;
        }
    }

    private int ctoi(char c) {
        return c-'a';
    }
}

 

 

코드 (next permutation 버전) : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

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

    private void solution() throws Exception {
        char[] arr = br.readLine().toCharArray();
        Arrays.sort(arr);
        int ans = 0;
        do {
            boolean chk = true;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] == arr[i-1]) {
                    chk = false;
                    break;
                }
            }
            if (chk) ans++;
        } while (nextPermutation(arr));
        System.out.println(ans);
    }

    boolean nextPermutation(char[] arr) {
        for (int a = arr.length - 2; a >= 0; --a) {
            if (arr[a] < arr[a + 1]) {
                for (int b = arr.length - 1; ; --b) {
                    if (arr[b] > arr[a]) {
                        char t = arr[a];
                        arr[a] = arr[b];
                        arr[b] = t;
                        for (++a, b = arr.length - 1; a < b; ++a, --b) {
                            t = arr[a];
                            arr[a] = arr[b];
                            arr[b] = t;
                        }
                        return true;
                    }
                }
            }
        }
        return false;
    }
}