[백준 9081] 단어 맞추기 (Next Permutation 알고리즘)

🍎[백준 9081] 단어 맞추기

문제링크

https://www.acmicpc.net/problem/9081

9081번: 단어 맞추기

 

⚾ 코드

c = int(input())


def solution(s):
    k = -1
    for i in range(len(s)-2, -1, -1):
        # 뒤에서 부터 돌면서, i가 i+1보다 작은 문자를 찾는다.
        if s[i] < s[i+1]:
            k = i
            break

    if k == -1:
        # 그러한 문자가 없다면, 원래 문자가 가장 큰 것.
        return s

    for i in range(len(s)-1, k, -1):
        # 역순으로 돌면서
        # k번째보다 뒤에 있는 문자들 중에서 s[k]보다 큰 값을 찾는다.
        if s[k] < s[i]:
            m = i
            break

    s[k], s[m] = s[m], s[k]  # 스와이프
    return s[:k+1]+list(reversed(s[k+1:]))  # k이후의 문자열을 역순을 취하고 리턴한다.

for _ in range(tc):
    s = list(input())
    answer = solution(s)
    print("".join(answer))

 

🔔 해결 과정 & 깨달은 점

풀이를 하는데 꽤 헤맸다. 검색을 통해서 알아봤지만 정확하게 이해하는데 까지 시간이 걸렸다.

먼저 문자열을 뒤에서 부터 돌면서 오름차순이 된 부분을 찾는다. (s[i] < s[i+1] 인 부분)

i는 스와이프를 시작할 지점이므로 k로 저장해둔다.

k가 만약에 갱신되지 않았다면, 그 문자열은 전체 내림차순 정렬이 되어 있는 문자열이므로, 해당 문자열이 가장 큰 문자열이다.

 

k가 갱신 되었다면,  다음 단계를 진행한다.

k번째 이후의 문자열을 역순으로 탐색하면서 s[k]보다 큰 문자를 찾는다. 

s[k]와 방금 찾은 s[i]를 스와이프 한다.

스와이프 한 부분 이후를 역순을 취해준다.

 

나는 여기서 의문이 들었다. 왜 역순을 취해주는 것일까?

 

결론은 다음과 같다.

k 이후의 문자열은 내림차순으로 정렬되어 있는 상태이다.
그러한 상태에서 뒤에서 부터 돌면서 k보다 큰 문자를 찾으면, 그 문자가 k 자리에 올 수 있는 가장 작은 문자가 되는 것이다.
스와이프 후 k 이후의 문자열을 역순을 취하면 k 다음으로 가장 작은(빠른) 문자열이 된다.

 

숫자로 생각해보자.

 

1 3 4 6 5 2

이 경우를 보면 s[k]는 우선 4이다.

s[k]보다 뒤에 있는 숫자 중에서 뒤에서 부터 볼때 s[k]보다 큰 것은 5이다.
4와 5를 스와이프하면 1 3 5 6 4 2 가 된다. (1 3 4 6 5 2 -> 1 3 5 6 4 2)

5 6 4 2 를 잘 보자.

원래는 뒤의 세 자리가 6 5 2였다. 

이게 지금 6 4 2가 되었다. 

이 숫자를 뒤집으면 2 4 6이 되고, 이는 6, 4, 2를 가지고 만들 수 있는 수 중에 가장 작은 수일 것이다.

근데 만약에 앞에서 부터 찾았다고 하면 (1 3 4 6 5 2 -> 1 3 6 4 5 2)가 될 것이고, k의 자리에 올 수 있는 4보다 크고 6보다 작은 5가 존재함에도 불구하고 6이 오게 된다. 따라서 뒤에서 부터 찾아야 하는 것이며, 역순을 취하면 다음으로 작은 수가 된다.

 

(참고로 이게 Next Permutation 알고리즘이라고 한다. 말 그대로 다음에 올 순열을 찾는 것이다.

c++에는 stl에 next_permutation 함수가 존재한다고 한다.)