(BOJ)기초(브루트포스)(5) 다음 순열 10972

작성일 | In

다음 순열

5. 다음 순열

  • 1부터 N까지의 수로 이루어지 순열이 있다.

  • 이 때, 사전순으로 다음에 오는 순열을 구하는 프로그램

  • 첫째 줄에 입력으로 주어지 순열 다음에 오는 순열을 출력한다.

  • 재귀로 순열을 구한 뒤, 구할 때마다 배열에 넣고, 그 뒤 인덱스를 찾아서 센다 ?

  • 이 방법으로 구해보려고 했으나, 재귀로 구현할 시, 한 배열에 출력한 값을 다 저장해주는 걸 못하겠다.

  • library는 쓰고 싶지 않았기에, 규칙을 찾아보기로 하였다.
  1. 배열의 이름을 a라고 하자
  2. 인덱스가 i가 0보다 크고, a[i-1]>= a[i]를 만족하면 인덱스 i를 1씩 반복적으로 감소시킨다.
  3. 반복문을 벗어난 후 인덱스 i가 0 이면 다음 순열이 존재하지 않으므로 false를 반환한다
  4. a[i-1]>=a[j]를 만족하면, 인덱스 j를 1씩 반복적으로 감소시킨다.
  5. a[i-1]의 값과 a[j]의 값을 맞바꾼다.
  6. a[i]부터 순열의 마지막까지 순서를 뒤집는다.
  7. 마지막으로 true를 반환한다. 다음 순열을 배열 a에 저장되어 있다.
def next_permutation(a):
    n = len(a) - 1
    i = n # i 구하기
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n # j 구하기
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n # j 다시 n으로
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1, j -= 1
    return True


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

if next_permutation(a) is True:
    for i in a:
        print(i, end=' ')
    print()
else:
    print(-1)

참고자료

코드플러스 참고블로그

0%