[LeetCode, 리트코드] Next Permutation
- 카테고리 없음
- 2018. 11. 27. 21:51
반응형
1. Problem
정수의 배열이 주어질 때, 이것의 다음 순열을 구하라. 예를 들면
1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
2. Solution
순열의 성질을 잘 알아야한다. 완전히 역배열된 5,4,3,2,1 과 같은 순열이 있다. 이 다음 순열은? 바로 1,2,3,4,5 다. 이 성질을 이용해서 문제를 풀면 어렵지 않게 풀 수 있다.
더 예를 들어보면 1,6,9,5,4,2,1 이라는 순열이 있다. 그 다음 순열은 어떻게 되겠는가? 9,5,4,2,1은 역배열이다. 그렇다면 6,9,5,4,2,1 에서 6을 대체할 다음 수는 바로 9이다. 왜냐하면 그래야지 나머지 새로운 정배열된 순열을 생성할 수 있기 때문이다. 즉 9,1,2,4,5,6 이 된다.
여기서 규칙을 발견할 수 있다. 먼저 역배열된 순열에서 이 역배열을 깨는 최초의 수를 찾는다. 이 수의 인덱스를 i라 하자. 그리고 이 i보다 큰 인덱스 중에서 이 최초의 수 바로 다음으로 큰 수를 찾는다. 그리고 그것들을 스왑한다.
스왑을 하고 난 후 이 i 인덱스 이후의 순열들을 뒤집는다. 이 규칙을 잘 적용하면 풀 수 있는 문제다.
3. Code
class Solution { public: void nextPermutation(vector<int>& nums) { int i = nums.size() - 2; int j; while(i >=0 && nums[i] >= nums[i+1]){ --i; } if(i == -1){ reverse(nums.begin(), nums.end()); } else{ j = i+1; while(j < nums.size() && (nums[j] - nums[i]) > 0){ j++; } swap(nums[i], nums[j-1]); reverse(nums.begin()+i+1, nums.end()); } return; } };
반응형
이 글을 공유하기