[코드트리/INTERMEDIATE LOW] 거꾸로 순열 (JAVA)

🔺 문제

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

🧩  해결 아이디어

• 백트래킹 (순열)

- 가능한 모든 순열 거꾸로 탐색 (큰 수부터 거꾸로 백트래킹 진행)

- 시간 복잡도 : O(N! *N)

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static List<Integer> permutation = new ArrayList<>();
    static boolean[] visited;
 
    static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        visited = new boolean[N + 1];
 
        getPerm(0);
        System.out.println(sb);
    }
 
    private static void getPerm(int num) {
        if(num == N) {
            printPerm();
            return;
        }
 
        // 뒤에서부터 하나씩 원소 선택
        for(int i = N ; i >= 1 ; i--) {
            if(visited[i])  continue;
 
            visited[i] = true;
            permutation.add(i);
 
            getPerm(num + 1);
 
            visited[i] = false;
            permutation.remove(permutation.size() - 1);
        }
    }
 
    private static void printPerm() {
        for(int i = 0 ; i < permutation.size() ; i++) {
            sb.append(permutation.get(i) + " ");
        }
        sb.append("\n");
    }
}

 

 

 

---

💬 느낀 점

재밌는 백트래킹...

 

1회독	2회독	3회독	4회독	5회독
V