다음 순열

2021-01-21

itertools 라이브러리의 permutations, combinations, product 함수를 이용하면 간단히 순열과 조합을 구성할 수 있다. 하지만 시간복잡도 때문에 문제 풀이에서 십중팔구 시간초과가 나게 마련. 순열을 구하는 기본 탐색 방법을 익혀두는 게 좋다.

  1. 리스트([1, 4, 3, 2])의 맨 뒤부터 탐색(2￫3￫4￫1)한다. 더 작은 숫자(1)가 나오면 멈춘다.
    1. 더 작은 숫자의 인덱스 값을 k로. (여기서는 1의 인덱스이므로 k=0)
  2. 다시 맨 뒤부터 k 바로 앞까지 탐색. 인덱스 k의 값(1)보다 큰 수(2)가 나오면 두 수를 스왑.
    1. 여기선 1과 2를 스왑. ([2, 4, 3, 1])
    2. 2의 인덱스를 m으로 한다.
  3. 인덱스 k 이후 인덱스(m) 값부터 맨 끝까지 오름차순 정렬. ([1, 3, 4])
  4. 리스트의 [:m]([2])과 [m:]([1, 3, 4])를 합친다.
  5. 끝. ([2, 1, 3, 4])
w = list(input()) # ['e', 'a', 'b', 'c', 'd']
n = len(w)
k = -1
for i in range(n-1, 0, -1): # 맨 뒤부터 탐색
    if w[i-1] < w[i]: # 더 작은 숫자가 나오면(c<d)
        k = i-1 # 더 작은 숫자(c) 인덱스가 k(k=3)
        break
if k == -1: # 전체가 내림차순으로 돼 있는 경우
    print('-1')
else:
    for j in range(n-1, k, -1): # 다시 뒤부터 인덱스 k까지 탐색
        if w[k] < w[j]: # w[k](c)보다 더 큰 수(d)가 나오면
            w[k], w[j] = w[j], w[k] # 두 수(c, d)를 스왑
            break
    tmp = sorted(w[k+1:]) # w[k](d) 이후부터 오름차순 정렬
    res = w[:k+1] + tmp # ['e', 'a', 'b', 'd'] + ['c']
    print(res) # ['e', 'a', 'b', 'd', 'c']

함수로 구현해보면,

def permutation(l):
    n = len(l)
    k = -1
    for i in range(n-1, 0, -1): 
        if l[i-1] < l[i]:
            k = i-1
            break
    if k == -1:
        return '-1'
    else:
        for j in range(n-1, k, -1):
            if l[k] < l[j]:
                l[k], l[j] = l[j], l[k]
                m = k+1
                break
        tmp = sorted(l[m:])
        res = l[:m] + tmp
        return res
l = list(input())
print(permutation(l))

[문제 보기]