[백준 JAVA]1342번: 행운의 문자열(계수정렬/순열)

1.문제

민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작했다. 준영이는 문자열 S에 나오는 문자를 재배치하면 서로 다른 행운의 문자열이 몇 개 나오는지 궁금해졌다. 만약 원래 문자열 S도 행운의 문자열이라면 그것도 개수에 포함한다.

2. Solved.ac 난이도

 3. 활용 알고리즘:  계수정렬 /순열

 

4. 틀린 이유: MLE

기본적으로 순열을 구하려면 정렬을 하고 시작하라는 말이 괜히 있는게 아니었다...
특히 알파벳처럼 a~f까지 범위가 한정적인 input에 대해서는 계수정렬을 사용하는 것이 아주 좋은 것 같다.

---

시도1. (MLE)

처음엔 입력받은 input 문자열을 순서대로 고려할 원소로 두고 순열을 구했다.(사용한 순열알고리즘 코드는 이전 게시글에 다양하게 정리해놓음)

그러다보니 사용한 알파벳도 체크해야하고(used) 중복된 문자열결과도 해결해야해서(hashset) 정말 많은 저장공간을 사용했고... 메모리 초과가 난 것이 원인이었다!

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

public class prob1342_행운의문자열 {

    static String str;
    static Boolean [] used;
    static int cntS;
    static HashSet<String> set= new HashSet<>();
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        str=in.readLine();
        used=new Boolean[str.length()];
        Arrays.fill(used,false);
        countString(0, new StringBuilder());
        System.out.println(set.size());
    }

    private static void countString(int cnt, StringBuilder s) {
        if(cnt==str.length()){
            set.add(s.toString());
            return;
        }
        for (int j = 0; j < str.length(); j++) {
            if (!used[j]&&(cnt==0||s.charAt(cnt-1)!=str.charAt(j))) {
                used[j]=true;
                s.append(str.charAt(j));
                countString(cnt + 1,s);
                s.deleteCharAt(s.length()-1);
                used[j]=false;
            }
        }
    }
}

 

최종 정답 코드

input 문자열이 소문자 알파벳으로 이루어져 있기 때문에 input 문자열의 원소에 대해서 계수정렬을 수행하였다(avail)

계수정렬 결과 배열은 순열에 사용 가능한 문자의 수라는 뜻에서 avail이라고 이름을 붙였고

이를 바탕으로 재작성하였더니 메모리 리밋없이 코렉을 받을 수 있었다!

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

public class Main {

    static String str;
    static int [] avail= new int[26];
    static int cntS;
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        str=in.readLine();
        for (int i = 0; i < str.length(); i++) {
            avail[str.charAt(i)-'a']++;
        }
        countString(0,0);
        System.out.println(cntS);
    }

    private static void countString(int cnt,int last) {
        if(cnt==str.length()){
            cntS++;
            return;
        }
        for (int j = 0; j < 26; j++) {
            if (avail[j]>0&&(cnt==0||last!=j)) {
                avail[j]--;
                countString(cnt + 1,j);
                avail[j]++;
            }
        }
    }
}