백준 - 모든 순열(Java)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 :https://www.acmicpc.net/problem/10974

 

[문제 설명]

1~N까지의 숫자를 줄 세우는 방법(순열)을 모두 출력하시오.

 

[접근 방법]

단순한 완전탐색 문제, 

각 숫자마다 N번씩 반복하므로

N^N -> 8^8 -> 2^24 => log2가 대략 0.3010이므로 8자리 숫자가 나올 듯하다.

시간제한이 1초이므로 대략, 100,000,000 연산보다 작아야한다.

우리가 푼 방법의 시간복잡도는 8자리 숫자이므로 9자리 숫자인 제한 조건에 비해 굉장히 널널하다.

 

[Java 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        boolean[] isVisited = new boolean[N];

        int idxOfCurrentNode = 0;
        int[] answer = new int[N];
        recursion(idxOfCurrentNode, isVisited, answer);
        System.out.println(sb);
    }

    private static void recursion(int idxOfCurrentNode, boolean[] isVisited, int[] answer) {
        if (idxOfCurrentNode == isVisited.length) {
            for (int i : answer) {
                sb.append(i);
                sb.append(" ");
            }
            sb.append("\n");
        }

        for (int i = 0; i < answer.length; i++) {
            if (isVisited[i]) {
                continue;
            }
            isVisited[i] = true;
            answer[idxOfCurrentNode] = i+1;
            recursion(idxOfCurrentNode+1, isVisited, answer);
            isVisited[i] = false;
            answer[idxOfCurrentNode] = 0;
        }
    }
}