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

들어온 문자열의 알파벳 개수를 세서 배열에 저장한다.
새로운 문자열을 생성해서 개수가 0이 아닌 알파벳을 붙인다.
생성된 문자열에 개수가 0 이상이고, 문자열의 맨 뒤 알파벳과 같지 않은 알파벳을 붙여준다.
재귀호출하여 문자열 뒤에 알파벳을 계속 붙여준다.
생성된 문자열의 길이가 처음 들어온 문자열의 길이와 같아지면 정답에 1을 더하고 리턴한다.

 

int [] counts = new int[26];
int idx = (int)input.charAt(i)-'a';
counts[idx]++;

 

아스키코드를 이용해서 알파벳의 개수를 셌다.
(해시맵으로 했다가 너무 오래걸리는 거 같아서 수정함~!)

 

void check(String str, String input){
        if (str.length() == input.length()){
            ans++;
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0 && str.charAt(str.length()-1)!=(char)('a'+i)){
                counts[i]--;
                check(str + (char)('a' +i), input);
                counts[i]++;
            }
        }
    }

 

알파벳의 개수가 0이상이고, 문자열의 맨 뒤 알파벳과 같지 않은 경우 알파벳의 개수를 1개 줄이고(알파벳 사용) 문자열에 알파벳을 더하고 재귀호출한다.
만들어진 문자열의 길이가 원래 들어온 문자열의 길이와 같아지면 정답에 1을 더하고 돌아간다.

 

예시

문자열 'abc'가 들어온 경우

 

a->ab->abc
->ac->acb
->b->ba->bac
->bc->bca
->c->ca->cab
->cb->cba

 

의 순서로 진행된다.

 

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

public class LuckyStr {

    static int ans = 0;
    static int [] counts = new int[26];
    static void check(String str, String input){
        System.out.println(str);
        if (str.length() == input.length()){
            ans++;
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0 && str.charAt(str.length()-1)!=(char)('a'+i)){
                counts[i]--;
                check(str + (char)('a' +i), input);
                counts[i]++;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        for (int i = 0; i < input.length(); i++) {
            int idx = (int)input.charAt(i)-'a';
            counts[idx]++;
        }
        for (int i = 0; i < 26; i++) {
            if (counts[i] > 0){
                counts[i]--;
                check((char)('a' +i) + "", input);
                counts[i]++;
            }
        }
        System.out.println(ans);
    }
}

 

결과

 

문제	결과	메모리	시간	언어	코드 길이
1342	맞았습니다!!	295620 KB	700 ms	Java 11	1144 B