[코딩테스트] 다음 순열(10972)

순열 문제는 진짜 너무 감이 안온다....ㅠㅠ

다음 순열

next_permutation은 직접 알고리즘을 통해서 구해야한다. 처음에 위 문제를 재귀, 파이썬의 permutation으로 풀려고하니 시간초과 메모리초과등 초과란 초과는 발생했다. 다음의 알고리즘을 이해해야하만 풀 수 있는 문제이다.

실패.

from itertools import permutations
import sys

input = sys.stdin.readline

n = int(input())
perm = list(map(int,input().split()))

permutation = list(permutations(range(1,n+1),n))
cnt = 0
for idx,i in enumerate(permutation):
	if i == tuple(perm):
		cnt = idx+1
if cnt == len(permutation):
	print(-1)
else:
	print(*permutation[cnt])

성공.

N = int(input())
input_array = list(map(int, input().split()))

for i in range(N - 1, 0, -1):  # 마지막 항부터 돈다
    if input_array[i - 1] < input_array[i]:  # 만약 앞 열의 값이 그 뒷열의 값보다 작다면
        for j in range(N - 1, 0, -1):  # 다시 그 앞 열의 값을 맨 뒷열부터 비교
            if input_array[i - 1] < input_array[j]:  # 그 앞열의 값이 뒤에 있는 어느 열보다 작다면
                input_array[i - 1], input_array[j] = input_array[j], input_array[i - 1]  # 그 두 값을 스왑
                input_array = input_array[:i] + sorted(input_array[i:])  # i-1 번째 까지의 리스트와 그 뒤에리스트를 정렬한 채로 붙인다.
                print(*input_array)  # *를 이용해 리스트 내부의 원소들을 공백을 사용하여 출력
                exit()  # 코드 종료

print(-1)  # 만약 위에서 코드 종료가 일어나지 않았다면(마지막 항이라면) -1 출력

1 4 3 2를 예시로 알고리즘을 알아본다.

• 뒤에서부터 순열을 비교하며, 뒷 값이 앞 값보다 큰 경우까지 반복한다. (3,2), (4,3)은 해당하지 않고, (1,4)가 해당된다.
  • 이 때, 1의 인덱스를 x라고 칭한다.
  • 4의 인덱스는 y라고 한다.
• 다시 뒤에서부터 값을 비교하며 인덱스 x보다 큰 값이 있으면 그 값과 swap한다.
  • 1과 2를 비교했고, 2가 크기 때문에 이 둘을 swap한다.
• y에 해당하는 인덱스부터 sort(오름차순정렬)를 한 뒤에 이어 붙인다.
  • 4 3 1을 sort해서 1 3 4가 된다.
  • 이어 붙이기 때문에 2 1 3 4가 된다.

참조. https://ji-gwang.tistory.com/262