[코드트리/INTERMEDIATE LOW] 크기가 n인 순열 (JAVA)

🔺 문제

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

 

🧩  해결 아이디어

• 백트래킹 (순열)

- 방문 배열 : 중복 방지용

- 앞에서부터 원소 선택하고, 선택하지 않은 원소들 중 가장 앞에 있는 원소들 선택

 - N개 모두 뽑았을 때, 해당 순열 출력

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

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static boolean[] visited;
    
    static List<Integer> combination = new ArrayList<>();
    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];
 
        back(0);
        System.out.println(sb);
    }
 
    private static void back(int num) {
        // 모든 원소 선택 시, 해당 순열 출력
        if(num == N) {    
            printAnswer();
            return;
        }
 
        // 앞에서부터 하나씩 원소 선택
        for(int i = 1 ; i <= N ; i++) {
            if(visited[i])  continue;
 
            visited[i] = true;
            combination.add(i);
 
            back(num + 1);
 
            visited[i] = false;
            combination.remove(combination.size() - 1);
        }
 
    }
 
    // 순열 출력 메소드
    private static void printAnswer() {
        for(int i = 0 ; i < combination.size() ; i++) {
            sb.append(combination.get(i)).append(" ");
        }
        sb.append("\n");
    }
}

 

---

💬 느낀 점

순열과 조합 코드 작성하는 방식 좀 다름!

visited 배열 왜 쓰는지도 이제 좀 더 알겠음

 

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

---

(참고)

✔ 코드트리