[Baekjoon] 10973번 이전 순열
Updated:
문제
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을 출력한다.
예제
Example 1:
Input:
4
1 2 3 4
Output:
-1
Example 2:
Input:
5
5 4 3 2 1
Output:
5 4 3 1 2
조건
시간 제한 : 1초
메모리 제한 : 256 MB
풀이과정
풀이 1
n = int(input())
arr = list(map(int, input().split()))
ans = -1
res = []
for i in range(n-2,-1,-1):
if arr[i] > arr[i+1]:
ans = i
for j in range(i+1, n):
if arr[j] < arr[i]:
sub = j
arr[i], arr[sub] = arr[sub], arr[i]
res += arr[:i+1]
res += arr[i+1:][::-1]
print(" ".join(map(str, res)))
break
else:
print(-1)
Leave a comment