LC1053: Previous Permutation With One Swap

작성일

https://leetcode.com/problems/previous-permutation-with-one-swap

  • 분명 잘못 생각한 답이 Accept 되어서 당황스럽다.
  • 풀이는 이렇다. 뒤쪽부터 찾을때 가장 처음으로 역전이 나오는 위치를 기준으로 그보다 바로 작은 것 과 위치를 바꿔라
  • 출제자가 잘못 생각한것이, 바꿔야 할 위치가 여러개 인경우 그것을 가장 뒤를 기준으로 바꾼 것인데, 가장 앞을 기준으로 해야 맞다.
  • 나는 map을 이용해서 $O(logN)$ 풀이를 했는데, Discuss를 보니 아니나 다를까 $O(N)$ two-point 풀이가 존재한다. :( 복습하자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& A) {
        map<int,int> pool;
        pool[A.back()] = A.size()-1;
        for(int i = A.size()-2; i >= 0; i--) {
            pool[A[i]] = i;
            auto it = pool.lower_bound(A[i]);
            if(it != pool.begin()) {
                swap(A[i], A[(--it)->second]);
                break;
            }
        }
        return A;
    }
};