10974. 모든 순열

www.acmicpc.net/problem/10974

10974번: 모든 순열

 

next_permutation을 쓰면 쉽게 풀리지만 안쓰고 풀어보려고 했다.

10972. 다음순열 문제랑 거의 똑같다. 

그런데 이 문제를 풀면서 비트마스킹 방식으로 아예 안보고 다시 코드를 짜보다가 내가 지금까지

잘못 이해했던걸 깨닫고 처음부터 다시 해서 오래 걸린 문제.

어찌됐든 잘 이해하고 다시 풀었다.

 

#include <iostream>
using namespace std;
#include <bitset>

bitset<20> b(0); /// bit masking
int a[20]; /// 순열

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {// 초기값 입력
        a[i] = i;
    }
    for (int i = 1; i <= n; i++) { // 초기값 출력
        cout << a[i] << " ";
    } cout << '\n';

    while (1) {
        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 구하기.


        if (idx < 1) break; // idx가 1보다 작으면 순열의 마지막값임.
        else {
            // 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] << " ";
            } cout << '\n';
        }
    }
}

 

 

그런데 처음에 개행할때 endl를 써서 풀었는데 16퍼쯤에서 시간초과가 났다.

endl이 buffer를 비우기까지 해서 시간이 더 오래걸린다는걸 어렴풋이 듣긴했는데 이정도로 오래걸리는줄은 몰랐다.

'\n'를 썼더니 금방 체점이 완료됐다.