다음 순열

사전순으로 순열을 나열했을 때 주어진 순열 다음에 올 순열을 찾는 문제다. 만약에 주어진 순열이 n=3 일 때 3,2,1 과 같이 가장 마지막 순열이라면 -1을 출력한다.

1,2,3,4로 이루어진 순열의 일부분을 가져와 보았다. n=4 순열을 통해 이해해보자.

Crepe

빨간색으로 칠해놓은 부분이 끝으로 부터의 가장 긴 내림차순 순열들이다. 특정 순열과 다음 순열을 비교해보자.

Crepe

1 2 4 3

  • 1 2 4 3 순열의 빨간색 부분(가장 긴 내림차순 순열)은 ‘4 3’이다.
  • ‘4 3’이 모두 내림차순으로 정렬되었으니 다음은 그 앞에있는(빨간색 바로 앞에 있는 검은색 수) ‘2’가 바뀔 차례이다.
  • 이때, ‘2 4 3’을 정렬시키면 ‘2 3 4’가 되고, 2 바로 다음으로 오는 3이 2를 대체하게 된다.
  • 또한 3을 제외한 ‘2 4’는 오름차순 정렬되어 뒤에 따라붙게 된다.

2 4 3 1

  • 2 4 3 1 순열의 빨간색 부분은 ‘4 3 1’이다.
  • ‘4 3 1’이 모두 내림차순으로 정렬되었으니 다음은 그 앞에있는(빨간색 바로 앞에 있는 검은색 수) ‘2’가 바뀔 차례이다.
  • 이때, ‘2 4 3 1’을 정렬시키면 ‘1 2 3 4’가 되고, 바뀌어야 하는 숫자 ‘2’ 바로 다음으로 오는 숫자 3이 2이를 대체하게 된다.
  • 3은 2를 대체하게 되고, 나머지 ‘1 2 4’는 오름차순 정렬되어 뒤에 따라붙게 된다.


CODE

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

save = 0  # 내림차순이 시작되는 위치 저장
for i in range(n-1, -1, -1):
    if numbs[i] > numbs[i-1]:
        save = i
        break
    if i-1 == 0:
        save = 0
        break

if save == 0:
    print(-1)
    sys.exit()
#    수열 전체가 내림차순이면 다음 순열이 없음으로
#    -1 출력 후 시스템종료

front = numbs[save-1] #내림차순이 시작되는 부분 직전의 값
Descending = numbs[save:] #내림차순 부분

#정렬했을 때 front 값 보다 한단계 앞에 있는 수를 찾는다.
#그 수를 new_front에 저장
tmp = Descending+[front]
tmp.sort()
index_front = tmp.index(front)
new_front = tmp[index_front+1]
#tmp에서 new_front를 제외한 후 오름차순 정렬
tmp.remove(new_front)
tmp.sort()

answer = numbs[:save-1]+[new_front]+tmp
print(*answer)


이 문제와 비슷한 문제로 이전 순열, 모든 순열등이 있다.

이전 순열

이전 순열은 다음 순열과 비슷하게, 특정 순열이 주어지면 오름차순으로 정렬된 순열에서 해당 순열 이전의 순열을 찾는 문제다.

다음 순열과 푸는 방식은 거의 동일하다. 다음 순열에서 가장 긴 내림차순 순열을 찾았다면 이전 순열에서는 끝으로 부터 가장 긴 오름차순 순열을 찾아야 한다.

Crepe


CODE

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

save = 0  # 오름차순이 시작되는 위치 저장
for i in range(n-1, -1, -1):
    if numbs[i] < numbs[i-1]:
        save = i
        break
    if i-1 == 0:
        save = 0
        break
if save == 0:
    print(-1)
    sys.exit()
#    수열 전체가 오름차순이면 이전 순열이 없음으로
#    -1 출력 후 시스템종료

# 오름차순 시작되는부분 직전값보다 한단계 낮은 수를 저장하고
# 이외의 수들은 내림차순

front = numbs[save-1]
Ascending = numbs[save:]

tmp = Ascending + [front]
tmp.sort()
index_front = tmp.index(front)
new_front = tmp[index_front-1]

tmp.remove(new_front)
tmp.sort(reverse=True)

answer = numbs[:save-1]+[new_front]+tmp
print(*answer)


[다시 풀어보기]