풀이 아이디어

풀이 코드

import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Deque<Integer> q = new LinkedList<>();
    static boolean[] visited;
    public static void main(String[] args) throws IOException{
        int n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        permutaion(n, 0);
    }
    public static void permutaion(int n, int len) throws IOException{
        if (len==n){
            bw.write(q.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            bw.newLine();
            bw.flush();
            return;
        }
        for(int i=1;i<=n;i++){
            if(visited[i]==false){
                q.addLast(i);
                visited[i] = true;
                permutaion(n, len+1);
                q.removeLast();
                visited[i] = false;
            }
        }
    }
}

풀이 코드 최적화

• 버퍼에 쌓고 한 번에 출력
  위에 코드에서 버퍼가 넘칠까봐 len==n일 때마다 출력을 했는데
  그냥 마지막에 한번에 해줘도 잘 실행되었다.
• permutation 인자 int n 중복 사용제거
  n은 그냥 static으로 쓰면 되는데 함수 인자로 넣어주다보니
  계속 불필요한 메모리를 사용하고 있었다.
  그래서 int n -> static int n으로 바꿔주고
  permutation 인자에서 int n을 제거하니 불필요한 초기화가 없어지고
  메모리 사용량을 줄일 수 있었다.

import java.util.*;
import java.util.stream.Collectors;
import java.io.*;
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static Deque<Integer> q = new LinkedList<>();
    static boolean[] visited;
    static int n;
    public static void main(String[] args) throws IOException{
        n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1];
        permutaion(0);
        bw.flush();
    }
    public static void permutaion(int len) throws IOException{
        if (len==n){
            bw.write(q.stream().map(String::valueOf).collect(Collectors.joining(" ")));
            bw.newLine();
            return;
        }
        for(int i=1;i<=n;i++){
            if(visited[i]==false){
                q.addLast(i);
                visited[i] = true;
                permutaion(len+1);
                q.removeLast();
                visited[i] = false;
            }
        }
    }
}

최적화 결과