10972. 다음 순열
https://www.acmicpc.net/problem/10972
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
처음에 난이도가 실버3이고, 정답비율 43퍼길래 쉬운 문제인줄 알았는데 속은것 같다.
아마 43퍼는 permutation함수를 써서 나온 비율이 아닐까.
직접 풀어보려고 꽤 오래 들여다보고 이리저리 끄적여 봤는데(1씩 계속 더해서 모든 자리의 수가 서로 다른 다음의로 큰수를 구해볼까 했는데 아무리 생각해도 시간이 말이안되서 포기) 모르겠어서 구글링을 해봤다.
구글링하고 느낀점은 찾아본게 정답이었다 아마 계속 봐도 못풀었을것 같다 ㅋㅋ.
결국 이문제는 next_permutation 함수를 직접 구현하는 문제라고 할 수 있다.
여러 군데에서 찾아봤는데 내가 이해한것을 정리해본다.
1. 가장 뒤에 있는 감소순열을 찾는다. 즉 A[i-1] < A[i]인 가장 큰 i를 찾는다.
A : 2 1 5 4 3
// 내림차순
A에서 i = 2이다.
2. A[i-1]보다 큰 가장 오른쪽에 있는 수가 j이다.
A : 2 1 5 4 3
A[i-1] = 1 보다 큰 가장 오른쪽에 있는 수는 3. 즉 j = 4
3. A[i-1]과 A[j]를 Swap한다.
A : 2 1 5 4 3 (Swap) --> A : 2 3 5 4 1
// 내림차순
4. i 부터 끝까지 reverse.
A : 2 3 1 4 5
// 오름차순
코드
#include <iostream>
using namespace std;
#include <algorithm>
void Doswap(int* x, int* y) {
int temp = *x;
*x = *y;
*y = temp;
}
bool res(int *a, int n) {
int i_idx = -1;
for(int i = 0; i < n-1; i++) { // i_idx 구함
if(a[i] < a[i+1]) i_idx = i;
}
if(i_idx == -1) return false; // a[i] < a[i+1]인 i 값이 없다, 즉 사전순 마지막에 오는 순열이다.
int j_idx = 0; // j_idx: a[i_idx]보다 큰 가장 마지막 원소의 위치
for(int j = i_idx+1; j < n; j++) {
if(a[i_idx] < a[j]) j_idx = j;
}
Doswap(&a[i_idx], &a[j_idx]); // a[i_idx], a[j_idx]값을 서로 바꿈
reverse(a+i_idx+1, a+(n));
return true; // 다음 순열을 찾았음.
}
int main() {
int n;
cin >> n;
int a[10001];
for(int i = 0; i < n; i++) {
cin >> a[i];
}
if(res(a, n)) {
for(int i = 0; i < n; i++)
cout << a[i] << " ";
}
else
cout << "-1" << endl;
}bool형으로 함수를 만들어서 false가 반환되면 (이미 사전순 마지막에 오는 순열이면) -1를 print.
true 반환되면 변환된 배열 print.
추가로 reverse를 함수를 쓰지않고 직접 구현하면 어떻게 해야할지 찾아봤다.
A : 1 2 3 4 5 6 7 일때, 3~6을 reverse 한다고 하면
첫 인덱스 i = 2, 마지막 인덱스 j = 5이다.
while(i < j) {
swap(A[i], A[j])
i++; j--;
}이런식으로 i와 j의 위치를 바꿔주고 i값은 1증가, j값은 1감소한다.
solution
'bitset' 자료구조를 이용해 bit masking이라는 방법을 썼다.
bitset
int main() {
bitset<5> b(0); // 5bit 크기로 '0'으로 초기화하여 자료 생성.
b.set(0); // 0번째 비트를 참으로 설정
b.set(1); // 1번째 비트를 참으로 설정
cout << b << endl; // 00011 출력
b.set(); // 전체 비트 1로 설정
cout << b << end; // 11111 출력
b.reset(4); // 4번째 비트를 0으로 설정
for(int i = 0; i < 5; i++) cout << b.test(i); //11110 출력.
}
bitset는 인덱스가 반대이다.
b가 0001이면 b.test(0)을 찍으면 1 출력.
bit masking
{1,2,3,4} 배열이 있고 처음에 bitset은 모두 1로 초기화 되어있다.
맨 끝 4를 없에고 4의 마스킹도 제거한다.
그리고 4의값을 1증가 시켰더니 최대값은 4를 초과한다.
그럼 다음 비트로 이동한다.
3을 없에고 3의 비트마스킹도 제거.
3에서 1증가시 4.
4의 마스크가 0이므로 4를 마스킹.
이제 다시 4로가서 값을 1부터 증가시키면서 비트 마스킹확인.
1은 비트마스킹 1.
2는 비트마스킹 1.
3은 비트마스킹 0이므로 3선택.
{1,2,3,4}의 다음순열 {1,2,4,3} 완성.
수정
첫 비트 부터 시작
1. 없에고 마스킹 제거.
2-1. 값 증가 -> 크기 넘거나, 있는 숫자면 다음 비트로 (1번으로)
2-2. 값 증가 -> 증가된 값의 비트마스크 확인
3. 마스크가 0이면 해당 값 선택, 마스킹.
4. 이전 비트로 이동, 1부터 증가시미켜 마스킹 '0'인 숫자 선택. 마스킹 처리.
유사한 문제를 풀면서 다시 살펴봤는데, 위에 내가 정리한 솔루션은 내가 잘못 이해한것같다.
1. 마지막 비트에서 시작, 마스킹 제거.
2. 값 증가 -> 크기 넘으면 다음 비트.
-> 크기 안넘으면 그 값의 비트마스크 확인
-> '0'이면 시작 값 변경 시작할 index 찾음.
-> '1'이면 2번으로 이동.
이렇게 하면 값 변경 시작할 index값 찾음. a[idx]값은 이미 자기의 값을 찾은상태.
그러므로 idx+1부터 시작.
3. 1부터 증가시키면서 비트마스크 값이 '0'인 숫자 선택. 마스킹 처리.
#include <iostream>
#include <bitset>
using namespace std;
bitset<20> b(0); /// bit masking
int a[20]; /// 순열
int main() {
int n;
cin >> n;
/// 순열 입력, 인덱스 숫자와 맞추기 위해 1부터.
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int trigger = 1;
int idx = n;
b.set(); // bit 모두 set.
while (trigger) {
b.reset(a[idx]); // 마스킹 제거
while (1) {
++a[idx]; // 값 증가시켜서
if (a[idx] > n) { // 증가시킨값이 n보다 크면
idx--; // 다음 비트로
break;
}
else if (b.test(a[idx]) == 0) {
trigger = 0;
break;
}
}
} //// 여기까지가 값 변경 시작할 idx 구하기.
// a[idx]는 이전 while루프에서 ++a[idx]하면서 이미 자기 값 찾음.
b.set(a[idx]);
// 1부터 증가시키면서 비트마스크 값 '0'인 숫자 선택, 마스킹.
for (int i = idx + 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (b.test(j) == 0) {
a[i] = j;
b.set(j); // 1로 set
break;
}
}
}
for (int i = 1; i <= n; i++) { // 출력
cout << a[i] << " ";
}
}
다시 푼것 정답.. 잘못 이해해서 오래걸렸다..