문제 소개
양의 정수로 이루어진 배열 A가 주어집니다(단, 값은 중복될 수 있습니다). 이때 딱 한 번의 스왑, 즉 두 원소 A[i]와 A[j]의 위치를 서로 교환하는 연산만을 사용해 만들 수 있는 순열 중에서, A보다 작으면서 사전순으로 가장 큰 순열을 찾아야 합니다. 만약 그러한 순열이 존재하지 않는다면 원래 배열을 그대로 반환하면 됩니다.
예를 들어 배열이 [3, 2, 1]이라면, 2와 1을 서로 바꿔 [3, 1, 2]를 얻을 수 있습니다. [3, 1, 2]는 [3, 2, 1]보다 작은 순열 중 사전순으로 가장 큰 값입니다.
알고리즘 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- n := 배열 A의 길이
- left를 n-2부터 -1까지 역방향으로 반복합니다.
- left가 -1에 도달하면 A를 그대로 반환하고, 그렇지 않고 A[left] > A[left + 1]인 지점을 발견하면 반복을 종료(break)합니다.
- element := 0, index := 0으로 초기화합니다.
- right를 left + 1부터 n까지 순회하며 다음을 확인합니다.
- A[right] < A[left]이면서 동시에 A[right] > element라면, element = A[right], index = right로 갱신합니다.
- A[left]와 A[index]를 스왑합니다.
- A를 반환합니다.
동작 원리 자세히 살펴보기
이 알고리즘이 왜 올바른 결과를 보장하는지 단계별로 살펴보겠습니다.
1. 오른쪽에서부터 감소 지점 찾기
배열을 뒤에서부터 훑으며 처음으로 A[left] > A[left + 1]이 성립하는 위치를 찾습니다. 이 지점 이후의 부분 배열은 이미 오름차순으로 정렬되어 있으므로, 해당 위치의 값을 더 작은 값으로 바꿔야만 전체 순열을 줄일 수 있습니다. 만약 끝까지 그런 지점이 없다면 배열 전체가 이미 오름차순으로 정렬된 최소 순열이므로, 더 작은 순열은 존재하지 않습니다.
2. 교체할 최적의 값 선택
left 위치의 값을 줄이려면, 오른쪽 구간에서 A[left]보다 작은 값들 중 가장 큰 값을 골라야 결과 순열이 최대한 커집니다. 또한 후보 값이 여러 번 등장한다면 가장 왼쪽에 있는 인덱스를 선택하는 것이 유리합니다. 왼쪽 값을 가져오면 더 큰 값이 오른쪽에 남아 뒤쪽 부분 배열이 최대한 유지되기 때문입니다.
구현 예제
class Solution(object): def prevPermOpt1(self, A): n = len(A) for left in range(n-2,-2,-1): if left == -1: return A elif A[left]>A[left+1]: break element = 0 index = 0 for right in range(left+1,n): if A[right]<A[left] and A[right]>element: element = A[right] index = right temp = A[left] A[left] = A[index] A[index] = temp return A ob = Solution() print(ob.prevPermOpt1([4,2,3,1,3]))
입력
[4,2,3,1,3]
출력
[4, 2, 1, 3, 3]
복잡도 분석
배열을 최대 두 번 선형 탐색하므로 시간 복잡도는 O(n)이며, 추가 메모리를 거의 사용하지 않아 공간 복잡도는 O(1)입니다.