[백준 1342번 / java] 행운의 문자열

문제

1342번: 행운의 문자열 (acmicpc.net)

풀이

입력값이 작기 때문에 백트래킹으로 풀었는데 메모리 초과가 발생했다.

행운의 문자열을 만들 수 있는 모든 경우를 빠짐 없이 실행하기 때문이다.

 

만약 aabbbaa라면, abababa 한 가지가 답이다.

그러나 abababa를 만드는 모든 경우를 실행한다.

이때 재귀호출에 의해 너무 많은 배열이 생성된다.

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

public class boj_11508 {
    static String[] arr;
    static HashSet<String> hs = new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String str = br.readLine();
        arr = new String[str.length()];
        for(int i=0; i<str.length(); i++){
            arr[i] = str.substring(i, i+1);
        }

        String s = "";
        boolean[] check = new boolean[str.length()];
        select(s, check);

        bw.write(hs.size()+" ");
        bw.close();

    }
    static void select(String s, boolean[] check){
        if(s.length() == arr.length){
            hs.add(s);
            return;
        }
        for(int i=0; i<arr.length; i++){
            if(s.length()>0 && s.substring(s.length()-1).equals(arr[i])){ //같은 문자 제외
                continue;
            }
            if(check[i]) //이미 사용한 문자 제외
                continue;
            s += arr[i];
            check[i] = true;
            select(s, check);
            s = s.substring(0, s.length()-1);
            check[i] = false;
        }
    }

}

코드 1 : 백트래킹

한 스터디원은 백트래킹으로 풀었다.

 

같은 백트래킹이지만 이 방법은 메모리 초과를 발생시키지 않는다.

행운의 문자열을 만드는 모든 경우를 탐색하는 것이 아니라,  

알파벳의 종류와 개수를 저장해둔 후 이 재료로 행운의 문자열을 몇 개 만들 수 있는지 세는 것이다.

 

1. 재귀호출 시 마지막으로 선택된 문자를 전달한다.

2. 선택한 문자의 개수를 하나 감소시킨다.

3. 재귀호출한다.

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

public class boj_1342 {
    static String str;
    static int[] alphabet = new int[27];
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        str = br.readLine();
        //알파벳이 몇 갠지 세기
        for(int i=0; i<str.length(); i++){
            alphabet[str.charAt(i)-'a']++;
        }

        char c = ' ';
        select(c, 0);
        bw.write(ans+"");
        bw.close();

    }
    static void select(char c, int len){
        if(len == str.length()){
            ans++;
            return;
        }
        for(int i=0; i<27; i++){
            char now = (char)(i+'a');
            if(alphabet[i] == 0)
                continue;
            if(c == now) //같은 문자 제외
                continue;
            alphabet[i]--;
            select(now, len+1);
            alphabet[i]++;
        }
    }
}

 

코드 2 : next permutation

또 다른 스터디원은 next permutation으로 풀었다.

주어진 문자열의 모든 사전 순 정렬 결과 중 행운의 문자열을 만족하는 경우를 카운트한다.

1. 사전 순으로 다음 순열(next permutation)을 구해서 모든 경우의 수를 만든다.
2. 그 중 인접한 곳에 같은 문자가 없는 경우만 카운트한다.

 

next permutation은 나도 처음 보는 풀이 방식인데, 두 명이나 이 방법을 사용한 걸 보니 많이 쓰이는 방법인 것 같아 정리해두고 넘어가는 게 좋을 것 같다.

 

1. 뒤에서부터 크기가 증가하는 부분을 찾음 -> 이 부분을 기준으로 정한다.

2. 좌측 지점의 맨 오른쪽 숫자 = a라고 할 때, 우측 지점의 뒤에서부터 a보다 큰 수를 찾는다. 이 숫자를 b라고 하자.

3. a와 b를 스왑

4. 우측 지점의 모든 수를 오름차순 정렬한다.

 

c++에서는 헤더에 algorithm을 추가하면 next_permutation함수를 사용할 수 있다고 한다.

자바는 그런 기능이 없어서 직접 함수를 구현해야 한다.

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

public class boj_1342_1 {

    static char[] arr;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        arr = br.readLine().toCharArray();
        N = arr.length;

        Arrays.sort(arr);

        int ans = 0;

        A: do{
            for(int i=1; i<N; i++){
                if(arr[i-1] == arr[i]) //인접한 곳에 같은 문자 발견
                    continue A;
            }
            ans++;
        } while(np());

        bw.write(ans+" ");
        bw.close();

    }
    static boolean np(){
        //증가하는 부분 찾기 //i-1, i
        int i = N-1;
        while(i>0 && arr[i]<=arr[i-1]) i--;

        if(i==0) return false;

        //i~N-1에서 i-1보다 크지만 가장 작은 값 찾기 //뒤에서부터 찾으면 됨
        int j = N-1;
        while(arr[i-1]>=arr[j]) j--;

        //두 수를 스왑
        swap(i-1, j);

        //i~N-1을 오름차순 정렬
        int k = N-1;
        while(k>i) swap(k--, i++);

        return true;
    }
    static void swap(int x, int y){
        char tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}