[C언어 연습문제]강좌 18. Permutations of Strings(문자열 순열 표시 - next_permutation 직접 구현)

문자열 순열 표시 - next_permutation() 함수 구현

순열에 대한 내용입니다. 순열에 대한 수학적 지식과 알고리즘이 없는 백지상태에서는 해결하기 어려운 문제였던 것 같습니다.

학습(Study) & 목표(Objective) & 과제(Task)

문자열은 일반적으로 사전 순으로 정렬됩니다. 사전 순으로 정렬된다는 것은 가장 왼쪽의 글자를 비교해서 순서를 정해 정렬을 하게 된다는 의미입니다.

예를 들면, abd가 abc보다 크다(abc < abd) 라고 볼 수 있는데, d가 c보다 크기(c < d) 때문입니다. 또한, z가 y보다 크기 때문에 (z > y) z > yyy라고 볼 수 있습니다.

gh < ghij와 같이 똑같은 문자에 접두사가 붙어있는 문자가 있으면, 접두사가 없는 문자열이 더 사전적으로 작다고 볼 수 있습니다.

해결해야 할 문제는 사전식 순서로 정렬된 문자열 배열이 주어지면, 정확하게 사전 순으로 모든 순열을 표출하는 문제입니다. 만약 2개의 순열이 똑같이 보이면, 하나만 표출하면 됩니다.

예를 들어 s = [ab, bc, cd]이면, 6가지 순열이 올바르게 출력되어야 합니다.

ab bc cd

ab cd bc

bc ab cd

bc cd ab

cd ab bc

cd bc ab

문자열 s의 각 문자는 같은 문자가 2개 이상 존재할 수 있습니다.

예를 들면, s = [ab, ab, bc]

모든 요소가 일치하는 순열은 한 번만 표출이 되어야 합니다.

다시 말해, 문자열이 같은 배열 s[0] == s[1] 이라면, s[0] s[1] 또는 s[1] s[0] 하나만 표출이 되어야 합니다.

3개의 분리된 요소를 가진 3개의 요소 배열은 위에서 보이는 것처럼 6개의 순열을 하고 있습니다.

이 경우 s[0] = ab, s[1] = ab가 전환되는 3개의 매칭된 순열이 있으므로, 시각적으로 고유한 3개의 순열만 표출해야 합니다.

ab ab bc

ab bc ab

bc ab ab

입력 형식(Input Format)

처음 줄에는 정수 n을 입력받습니다. 정수 n은 문자열 배열의 길이입니다.

다음 n개의 줄은 다음 문자열 s[i]를 포함합니다.

제약 조건(Constraints)

2 <= n <= 9

1 <= |s[i]| <= 10

s[i]는 소문자 영어 알파벳으로 구성되어있음.

출력 형식(Output Format)

각 순열을 공백으로 구분된 문자열 목록으로 한 줄에 표출해야 합니다.

입력 예제(Sample Input) - 1

2

ab

cd

출력 예제(Sample Output) - 1

ab cd

cd ab

입력 예제(Sample Input) - 2

3

a

bc

bc

출력 예제(Sample Output) - 2

a bc bc

bc a bc

bc bc a

주어진 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int next_permutation(int n, char **s)
{
    /**
    * Complete this method
    * Return 0 when there is no next permutation and 1 otherwise
    * Modify array s to its next permutation
    */
}
 
int main()
{
    char **s;
    int n;
    scanf("%d", &n);
    s = calloc(n, sizeof(char*));
    for (int i = 0; i < n; i++)
    {
        s[i] = calloc(11, sizeof(char));
        scanf("%s", s[i]);
    }
    do
    {
        for (int i = 0; i < n; i++)
            printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, s));
    for (int i = 0; i < n; i++)
        free(s[i]);
    free(s);
    return 0;
}

답안 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int next_permutation(int n, char **s)
{
    for (int i = n - 1; i > 0; i--)
        if (strcmp(s[i], s[i - 1]) > 0)
        {
            int j = i + 1;
            for (; j < n; j++) if (strcmp(s[j], s[i - 1]) <= 0) break;
            char *t = s[i - 1];
            s[i - 1] = s[j - 1];
            s[j - 1] = t;
            for (; i < n - 1; i++, n--)
            {
                t = s[i];
                s[i] = s[n - 1];
                s[n - 1] = t;
            }
            return 1;
        }
 
    for (int i = 0; i < n - 1; i++, n--)
    {
        char *t = s[i];
        s[i] = s[n - 1];
        s[n - 1] = t;
    }
    return 0;
}

먼저 전제조건은, 이미 입력받은 데이터는 사전 순으로 들어와 있다는 내용입니다.

여러 가지로 복잡합니다. 설명이 무척 난감한 코드가 나왔습니다. 가장 좋은 방법은 적당한 예시를 잡고 순서대로 그려나가는 방법입니다. (예 : ab, bc, cd)

로직으로 들어가 보면 처음 for 문에 의해, 뒤에서부터 검사를 시작합니다.

뒤의 문자열이 정상적으로 사전 순으로 되어있고, (a, b, c)

if (strcmp(s[i], s[i - 1]) > 0) // 뒤의 문자가 사전 순이면

뒤의 문자열(c)보다 더 뒤에 있는 문자열(null)이 같거나 작거나, 없을 때까지 루프를 돕니다. a, b, c 첫 번째 loop을 예를 들었을 땐, 뒤에 데이터가 시작부터 없죠.

int j = i + 1;

for (; j < n; j++) if (strcmp(s[j], s[i - 1]) <= 0) break;

그러면, b(i-1)와 c(j-1)를 바꿉니다. a, c, b가 되겠죠. 그리고 i가 마지막 문자열 배열 인덱스(n-1)보다 작으면, 또 무언가를 계속 바꾸는데, i가 2로 n-1과 똑같아서 뒤집지 않고 return 1을 합니다.

            char *t = s[i - 1];
            s[i - 1] = s[j - 1];
            s[j - 1] = t;
            for (; i < n - 1; i++, n--)
            {
                t = s[i];
                s[i] = s[n - 1];
                s[n - 1] = t;
            }
            return 1;

그러면 제시된 main 함수에 의해 loop을 계속 돌면서 계속 검사를 하게 됩니다.

마지막 데이터죠. 문자열 배열을 완전히 뒤집습니다. 1, 2, 3, 4, 5는 5, 4, 3, 2, 1이 되겠죠.

    for (int i = 0; i < n - 1; i++, n--)

    {

        char *t = s[i];

        s[i] = s[n - 1];

        s[n - 1] = t;

    }

    return 0;

추가 답안 코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
void swap(char **s, int x, int y)
{
    char *temp;
    temp = s[x];
    s[x] = s[y];
    s[y] = temp;
}
 
void reverse(char **s, int x, int y)
{
    while (x < y)
    {
        swap(s, x, y);
        x++;
        y--;
    }
}
 
// n은 문자열 배열의 총 갯수 s는 문자열 배열 포인터
int next_permutation(int n, char **s)
{
    int i, inv = -1;
 
    // [STEP 0] sample : ab, bc, cd
    for (i = 0; i < n - 1; i++)
    {
        if (strcmp(s[i], s[i + 1]) < 0)
        {
            // [STEP 1] 사전순 마지막 부분 탐색 i = 1, bc, cd
            inv = i;
        }
    }
 
    if (inv == -1)
    {
        // 사전 역순으로 정렬됨 (마지막 데이터)
        return 0;
    }
 
    // 뒤에서부터 사전순 최초 위치까지 이동
    for (i = n - 1; i > inv; i--)
    {
        // 이동하면서 처음 발견 위치가 s[i]보다
        // 사전순으로 적으면, 자리를 바꾼다.
        if (strcmp(s[inv], s[i]) < 0)
        {
            // [STEP 2]  i = 2, s[inv] = bc
            // [STEP 3] s[i] = cd
            swap(s, inv, i);
            break;
        }
    }
 
    // [STEP 4] ab, cd, bc, inv + 1 = 2, n -1 = 2 
    reverse(s, inv + 1, n - 1);
 
    return 1;
}
 
int main()
{
    char **s;
    int n;
    scanf("%d", &n);
    s = calloc(n, sizeof(char*));
    for (int i = 0; i < n; i++)
    {
        s[i] = calloc(11, sizeof(char));
        scanf("%s", s[i]);
    }
    do
    {
        for (int i = 0; i < n; i++)
            printf("%s%c", s[i], i == n - 1 ? '\n' : ' ');
    } while (next_permutation(n, s));
    for (int i = 0; i < n; i++)
        free(s[i]);
    free(s);
    return 0;
}

좀 더 분석하기 쉬운 코드를 보겠습니다. 먼저 a, b, c, d 순으로 정렬된 마지막 index까지 찾아갑니다.

값이 a, b, c, d일 때, c, d가 마지막이므로, c의 index 2가 inv에 저장되겠죠.

    int i, inv = -1;

 

    for (i = 0; i < n - 1; i++)

    {

        if (strcmp(s[i], s[i + 1]) < 0)

        {

            inv = i;

        }

    }

inv 값이 초기화된 -1이면, 사전 역순으로 정렬되어 있으니, 마지막 데이터라는 의미겠죠?

    if (inv == -1)

    {

        // 사전 역순으로 정렬됨 (마지막 데이터)

        return 0;

    }

다시 문자열 배열의 맨 뒤의 index에서 사전 역순 마지막 데이터(index 2)보다 클 때까지 돌면서, 사전 역순 마지막 데이터보다 더 큰 값(사전 뒤에 정렬되는 값)인지 확인하고, 바꿔버립니다.

값이 a, b, c, d일 때, s[inv] 값이 c이므로, s[i] 값인 d랑 바꾸겠죠.

    // 뒤에서부터 사전순 최초 위치까지 이동

    for (i = n - 1; i > inv; i--)

    {

        // 이동하면서 처음 발견 위치가 s[i]보다

        // 사전순으로 적으면, 자리를 바꾼다.

        if (strcmp(s[inv], s[i]) < 0)

        {

            swap(s, inv, i);

            break;

        }

    }

사전 마지막 정렬된 값 이후부터의 값을 뒤집어 버립니다.

    reverse(s, inv + 1, n - 1);

왜 뒤집을까요?

정답은 뒤집으면 다음 순열이 정렬되기 때문입니다.

여기서부터 상세한 이해를 위해서는 수학적 지식인 '순열'을 알아야 합니다

(https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

기본적인 순열의 조건이 다음과 같습니다.

- s[i] < s[i+1]을 만족하는 인덱스가 없으면, 마지막 순열입니다.(기준의 역순)

1. s[i] < s[j]를 만족하는 i보다 가장 큰 인덱스 j를 찾습니다.

2. s[i]의 값을 s[j] 바꿉니다.

3. s[i+1] 이후 s[n-1], 즉 마지막 index까지의 값을 뒤집으면, 다음 순열의 값을 알 수 있습니다.

이 4가지 다음 순열을 찾는 조건을 알고 있으면, 구현하기 수월했을 것 같습니다.

수학적 지식이 필요했던 문자열 순열 표시 C언어 연습 문제였습니다.