1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | bool next_permutation(int *a, int n) { int i = n - 1l while (i > 0 && a[i - 1] >= a[i]) i -= 1; if (i <= 0) return false; // 마지막 순열 int j = n - 1; while (i<j) { swap(a[i], a[j]); i += 1; j -= 1; } return true; } | cs |
N개중에 일부를 선택해야하는경우.
재귀호출이나 비트마스크 사용하면 더쉬움
그래서 잘안씀
123더하기 9095번문제
1~N까지로 이루어진 순열
123
4123
겹치는수없음
크기는항상 N이 되어야하고 순서가 중요
N!
순열을 사전순으로했을때
첫순열 : 오름차순
마지막 ; 내림차순
예)
123
132
213
231
312
321
다음순열 -> 사전순으로했을때 사전순으로 다음에 오는 순열
C++ STL의 algorithm에는 이미 next_permutation 과 prev_permutation(이전순열) 이 존재함. 자바에없음 개꿀
다음순열 -> 순열의 마지막수에서 끝나는 가장 긴 감소수열 찾으면됨
크기가 n인 배열 a의 다음순열
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | bool next_permutation(int *a, int n) { int i = n - 1l while (i > 0 && a[i - 1] >= a[i]) i -= 1; if (i <= 0) return false; // 마지막 순열 int j = n - 1; while (i<j) { swap(a[i], a[j]); i += 1; j -= 1; } return true; } | cs |
차이를최대로 10819 문제 안품
외판원순회2 10971 문제 품
로또 6603 문제 품
연산자 끼워넣기 14888문제 품