BOJ 10972: 다음 순열

이번 문제는 저번에 풀었던 순열 관련 문제와 유사하다.

처음에 생각했던 방법은, 저번에 풀었던 것과 유사하게 dfs를 이용하여 푸는 것이였다.

 

n=int(input())
nums=list(map(int,input().split()))
answer=[]
result=[]
visited=[False]*(n+1)
def solve(d,n):
  if d==n:
    answer.append(result[:])
    return
  for i in nums:
    if not visited[i]:
      visited[i]=True
      result.append(i)
      solve(d+1,n)
      visited[i]=False
      result.pop()

solve(0,n)
answer.sort()

a=answer.index(nums)
if nums==answer[-1]:
  print(-1)
else:
  print(' '.join(map(str,answer[a+1])))

그러나, 이 방법을 사용하면 Recursion Error가 뜬다.

최대 10000가지의 숫자를 다뤄야하는 만큼, 재귀가 너무 많이 사용된다.

 

그래서 검색 후 찾은 방법은.....

---

Next Permutation 알고리즘이다.

순열과 조합 생성 시 재귀적으로 구현하지 않고 각 인덱스를 비교한다.

 

1. 뒤쪽부터 탐색함. 

마지막 인덱스가 i번째라면, 그 전인 i-1번째와 비교한다.

i-1의 value < i의 value를 찾는다. (뒤에가 더 큰 경우를 찾는다.)

만약 앞에 있는 수가 제일 큰 Reverse Sort 상황이면, 종료한다.

 

2. 뒤쪽부터 탐색하여 교환할 숫자와 그보다 더 큰 값을 찾고, 서로 교환

 

3. 이후 바꾼 인덱스부터 sort

n=int(input())
nums=list(map(int,input().split()))
x=0
for i in range(n-1,0,-1):
  if nums[i-1]<nums[i]:
    x=i-1
    break
def solve(nums):
  for i in range(n-1,0,-1):
    if nums[x]<nums[i]:
      nums[x],nums[i]=nums[i],nums[x]
      nums=nums[:(x+1)]+sorted(nums[(x+1):])
      print(' '.join(map(str,nums)))
      return
  print(-1)

solve(nums)

 

진짜... 이런 알고리즘은 어떻게 만든거야...!!!