[백준 10973] 이전 순열

문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

---

풀이

앞서 풀었던 다음 순열과 비슷하게 접근하여 풀면 될 것 같다

먼저 이전 순열을 구하기 위해 수열을 나열해보고 규칙을 찾아보자

 

N = 4 인 경우,

1 2 3 4

1 2 4 3

1 3 2 4

1 3 4 2

1 4 2 3

1 4 3 2 

2 1 3 4

2 1 4 3

.

.

.

순열의 특성 상 0번 인덱스 자리에 가까울수록 사용되지 않은 작은 수가 우선적으로 배치된다.

따라서 현재 수열의 마지막 인덱스부터 역순으로 진행되는 내림차순에 위배되는 인덱스가 바로 전에 교환된 인덱스임을 알 수 있다.

 

2 1 3 4에서 (1 3 4)는 뒤에서부터 내림차순이 성립되기에 뒤에 (1 4 3)이라는 부분 수열을 만들수가 있다

하지만 2 1 3 4의 이전수열인 1 4 3 2에서 (4 3 2)를 보면 뒤에서부터 오름차순 특성을 띄고있기에 더이상 뒤에 만들 수 있는 사전순 부분수열이 존재하지 않는다.

그렇기에 뒤에서부터 시작한 내림차순이 끝나는 지점의 인덱스가 이전 수열에서 교환된 인덱스임을 유추할 수 있다

# 뒤에서부터 시작하여 내림차순의 마지막 인덱스 i 탐색
for e in reversed(arr):
    if line_value < e:
        break
    line_value = e
    line_index += 1
print(arr[-line_index])

 

 

인덱스 idx를 찾아냈다면 현재 수열보다 앞쪽에 배치된 수열이기에 해당 인덱스의 뒤쪽에서 arr[idx]보다 작은 수를 탐색해야한다. 하지만 바로 이전의 수열이기에 arr[idx] 보다 작은 수 중에서 가장 큰 수를 탐색하여 arr[idx]와 위치를 바꿔준다

# i~N중 arr[i]보다 작은 가장 큰 수의 인덱스 j를 탐색
for m in arr[-1:-line_index-1:-1]:
    if m < arr[-line_index-1]:
        break
    swap_idx += 1
print(arr[-swap_idx])

# i-1과 j swap
swap = arr[-line_index-1]
arr[-line_index-1] = arr[-swap_idx]
arr[-swap_idx] = swap

마지막으로 i~N인덱스를 뒤집어서 마지막 인덱스부터 역순으로 오름차순이 되도록 배치함으로써 arr[idx]인덱스가 바뀌어야 하는 상태의 마지막 부분수열을 형성하여 재결합한다.

# i~N인덱스 뒤집어서 재결합
arr = arr[:-line_index] + list(reversed(arr[-line_index:]))
print(*arr)