백준/10974 모든 순열

모든 순열

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

22942

14299

10825

63.053%

문제

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

---

 

순열 적용연습을 위한 기본순열문제이다.

순열은 

뽑을 전체 목록을 반복문으로 도는데 그때 반복문의 처음인덱스가 0이다.

0이므로 다양한 순서의 값들이 나온다.

중복을 원한다면 방문배열을 없애면 될것이다.

 

package practice;

import java.io.*;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int number = Integer.parseInt(br.readLine()); //입력받은수
        int[] arr = new int[number]; // 1 ~ 입력받은 수까지를 요소로 가지는 배열
        for(int i=1;i<=number;i++)
        {
            arr[i-1] = i; //1 ~ 입력받은 수까지를 요소로 가지는 배열
        }
        boolean[] visited = new boolean[number]; //방문배열
        int[] result = new int[number]; //결과를 저장할 배열 , 순열은 순서가 중요하므로 순서대로 저장하기위해 담을곳이 필요.

        permutation(arr,visited,0,result);

        bw.flush();
        bw.close();




    }
    static void permutation(int[] arr ,boolean[] visited,int count,int[] result  ) throws IOException
    {
        if(count == arr.length) //다 뽑았다면
        {
            for(int i=0;i<result.length;i++)
            {
                bw.write(result[i]+" ");
            }
            bw.newLine();
            return;
        }

        //뽑을 재료들을 전부 돌면서 깊이우선탐색한다 -> 깊이우선탐색으로 인해 결과는 사전순으로(3,1,2 -> 3,2,1)나온다. , 인덱스의 시작은 항상 0이므로 [1,2,3] [1,3,2와 같은 순서만 다른경우도 나온다.
        for(int i=0;i<arr.length;i++)
        {
            if(!visited[i])
            {
                visited[i] = true;
                result[count] = arr[i];
                permutation(arr,visited,count+1,result);
                visited[i] = false;

            }
        }


    }


}