BOJ_10974_모든 순열 (Java, C++)

[Silver III] 모든 순열 - 10974

문제 링크

성능 요약

메모리: 3896 KB, 시간: 16 ms

분류

백트래킹, 브루트포스 알고리즘

제출 일자

2024년 12월 29일 18:55:08

문제 설명

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

문제 풀이

순열은 재귀로 방문처리와 함께 작성할 수 있었다. 메모리 사용을 좋게 하고자 길이 8 제한을 보고 비트마스킹으로 방문처리를 했다.

C++에서 숫자를 문자로 만들기 위해 to_string 말고 stringstream을 사용해보았다. stringstream res에 « 하듯 입력했고 마지막에 cout « res.str()로 출력했다.

코드

Java 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	static int N, number[];

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		N = Integer.parseInt(br.readLine());
		number = new int[N];
		permutation(0, 0);

		bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}

	private void permutation(int depth, int visited) {
		if (depth == N) {
			for (int i = 0; i < N; i++) {
				sb.append(number[i]).append(" ");
			}
			sb.append("\n");
			return;
		}

		for (int i = 1; i <= N; i++) {
			if ((visited & (1 << (i - 1))) == 0) {
				number[depth] = i;
				permutation(depth+1, visited | (1 << (i-1)));
			}
		}
	}
}

---

C++ 코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int N;
vector<int> number;
stringstream res;

void permutation(int depth, int visited) {
    if (depth == N) {
        for (int i = 0; i < N; i++) {
            res << number[i] << " ";
        }
        res << "\n";
        return;
    }

    for (int i = 1; i <= N; i++) {
        if ((visited & (1 << (i - 1))) == 0) {
            number[depth] = i;
            permutation(depth + 1, visited | (1 << (i - 1)));
        }
    }
}

void solve() {
    cin >> N;
    number.resize(N);
    permutation(0, 0);
    cout << res.str();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    // cin >> tt;    // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}