[파이썬, Java] 10974. 모든 순열

문제

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

입력

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

출력

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

예제 입력 1 

3

예제 출력 1 

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

 

 

🐊 나의 풀이

import sys
input=sys.stdin.readline

N=int(input())
visited=[0]*(N+1)

def dfs() :
    if len(num) == N :
        print(num)

    for i in range(1, N+1) :
        if not visited[i] :
            visited[i]=1
            num.append(i)
            dfs()
            visited[i]=0
            num.pop()

num=list()
dfs()

백트래킹 풀이

'왜 안되지?'하다가 다른 사람의 풀이를 참고했다😅

visited로 체크하면서 반복한다.

 

 

import java.io.*;

public class Main{
    static int N;
    static boolean[] visited;
    static int[] arr;
    static StringBuilder sb=new StringBuilder();
    static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        arr=new int[N+1];
        visited=new boolean[N+1];
        dfs(0);
        bw.write(sb.toString());
        bw.flush();
    }

    public static void dfs(int depth) throws IOException{
        if(depth == N){
            for(int i=0; i<N; i++){
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
        }

        for(int i=1; i<=N; i++){
            if(!visited[i]){
                visited[i]=true;
                arr[depth]=i;
                dfs(depth+1);
                visited[i]=false;
            }
        }
    }
}

백트래킹 풀이

sb에 저장하는 과정에서 애를 좀 먹었다..

visited[i]=true 후 sb.append(i+" ")를 하고, depth==N이 되었을 때 맨 마지막 " " 삭제, \n 추가를 했었다.

이렇게 하니 1 2 3\n2 3\n 이런식으로 나왔다. 맨앞이 빠짐 ㅠ

int 배열 arr에 값을 저장 후 depth==N일 때 sb에 하나씩 넣어주니 제대로 된 결과를 얻을 수 있었다.

그리고 원소 삭제할 필요가 없다. arr[depth]에 값이 덮어씌워지니까 

 

 

# 실패
import sys
input=sys.stdin.readline

N=int(input())
visited=[0]*(N+1)

def dfs(depth, num, start) :
    if depth == N :
        print(num)

    for i in range(start, N+1) :
        #visited[i]=1
        num.append(i)
        dfs(depth+1, num, i+1)
        num.pop()


dfs(0, [], 1)

123만 떠서 실패 ㅠ

지금 보니 123만 나오는 게 당연하구나...

start 때문에 더이상 길이가 N이 되게 못 만든다.

 

 

# 실패
import sys
input=sys.stdin.readline

N=int(input())
visited=[0]*(N+1)

def dfs(depth, num, start) :
    if depth == N :
        print(num)

    for i in range(start, N+1) :
        if not visited[i] :
            visited[i]=1
            dfs(depth+1, num+str(i), i+1)
            visited[i]=0


visited[1]=1
dfs(1, "1", 1)

역시나 start가 없어야 한다.

 

 

🐝 다른 사람 풀이

from itertools import permutations
import sys

print=sys.stdout.write

def BOJ10974() :
    n=int(input())
    for i in map(" ".join, permutations([str(i) for i in range(1, n+1)])) :
        print(i+"\n")

BOJ10974()

permutations 메소드를 이용했다.

 

 

import java.io.*;

public class Main{
    static int N;
    static char[] arr;
    static boolean[] visits;
    static StringBuilder sb;

    public static void main(String[] args) throws IOException{
        try(BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out))){

            N=Integer.parseInt(br.readLine());
            sb=new StringBuilder(2*N*N*N);
            arr=new char[N];
            visits=new boolean[N];

            for(int i=1; i<=N; i++){
                visits[i-1]=true;
                arr[0]=(char)(i+'0');
                permutation(1);
                visits[i-1]=false;
            }
            bw.write(sb.toString());
            bw.flush();
        }
    }

    public static void permutation(int depth){
        if(depth == N){
            for(int i=0; i<N; i++){
                sb.append(arr[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for(int i=1; i<=N; i++){
            if(!visits[i-1]){
                visits[i-1]=true;
                arr[depth]=(char)(i+'0');
                permutation(depth+1);
                visits[i-1]=false;
            }
        }
    }
}

arr의 첫 원소로 0부터 N까지 넣어가며 permutation 메소드 호출한다.

sb에 넣고 BufferedWriter bw로 한번에 출력한다.

배열 arr의 타입을 char로 한 이유는 뭘까 🤔

어차피 toString 메소드를 쓸건데 ?!

 

 

문제 출처 👉 백준