백준 1342번 행복의 문자열 :: 마이구미

이 글은 백준 알고리즘 문제 1342번 "행복의 문자열" 을 풀이한다.

순열(permutation) 알고리즘을 통해 문제를 해결할 수 있다.

순열 알고리즘 이해 - http://mygumi.tistory.com/60

1342번 - https://www.acmicpc.net/problem/1342

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

행복의 문자열의 예는 다음과 같다.

aabbbaa
=> abababa

abc
=> abc
=> acb
=> bac
=> bca
=> cab
=> cba

주어지는 문자열에서 나타낼 수 있는 모든 경우를 탐색하면 된다.

무작정 탐색한다면, 시간 초과를 초래한다.

길이가 10이지만, abcdefghij와 같이 모두 다른 알파벳이 주어졌을 경우, 어마어마한 경우가 존재한다.

즉, 나타낼 수 있는 문자열의 경우에 대한 시간을 고려해야하는 문제가 된다.

순열 알고리즘을 사용하여 문제를 해결해야한다.

자세한건 위에서 명시한 참고 링크를 보길 바란다.

private void solve() {
    // http://mygumi.tistory.com/234
    char[] array = sc.next().toCharArray();
    int ans = 0;
    Arrays.sort(array);
    while (true) {
        if (isLuckey(array)) {
            ++ans;
        }
        if (!nextPermutation(array)) {
            break;
        }
    }
    System.out.println(ans);
}
 
static boolean isLuckey(char[] array) {
    int len = array.length;
 
    for (int i = 0; i < len - 1; i++) {
        if (array[i] == array[i + 1]) {
            return false;
        }
    }
    return true;
}
 
static boolean nextPermutation(char[] array) {
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) {
        i--;
    }
    // i는 증가하지 않은 가장 긴 접미사 인덱스
    // 1234 => 3 1243 => 2 1324 => 3 1342 => 2 1423 => 3 1432 => 1
    // 1243 43 증가하고 있지 않음으로 4의 인덱스. 1432 432 증가하고 있지 않으므로 4의 인덱스.
    // 현재 i는 접미사의 헤드 인덱스.
 
    // 마지막 변경이 되었을 때 4321일 경우 i는 위의 접미사 인덱스를 구하는 과정에서 -1이 됨.
    if (i <= 0)
        return false;
 
    // array[i - 1] 요소를 피벗으로 정함.
    // 위의 피벗과 스왑할 피벗을 초과한 가장 오른쪽 요소를 찾음.
    int j = array.length - 1;
    while (array[j] <= array[i - 1]) {
        j--;
    }
    // array[j] <= array[i - 1] 조건인 이유는.
    // array[j]는 array[i - 1]보다 항상 커야하기 때문이다.
    // => 사전 순으로 모든 경우의 수를 들려야하기 때문.
    // array[i - 1] 와 array[j]를 이용하여 새로운 피벗 구함.
    // array[j] 요소가 새로운 피벗이 된다.
    // Assertion: j >= i
 
    // 피벗 2개는 서로 스왑에 이용하기 위해 사용됨.
    // 새로운 피벗을 이용하여 스왑.
    char temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
 
    // 위의 과정이 일어나더라도 사전순으로 되지 않음.
    // 접미사 인덱스를 활용하여 반대로 만들어준다.
    j = array.length - 1;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        i++;
        j--;
    }
 
    // Successfully computed the next permutation
    return true;
}