[백준] code.plus(브루트포스-순열,JAVA)10974번, 모든 순열

문제 링크

10974번: 모든 순열

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

순열이란

n개의 원소를 중복없이 나열하는 것입니다.

순열 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 오름차순으로 이루어진 순열이다.

2. 1~N개의 수로 이루어져있다.

3. 순열을 만들 수 있는 모든 경우의 순열을 출력해야 한다.

 

배열

result  : 현재 경우의 순열

 

check : 순열에 들어갈 1~N값 사용되었는지 확인

 

result, check와 재귀를 이용하여 모든 경우의 순열을 구하였습니다.

 

문제에 해결알고리즘은

1. 1~N까지 순열에 들어갈 수을 check 배열 확인을 통해서 탐색합니다.

2. 순열을 완성시키면 StringBuilder에 저장합니다.

3. 재귀가 끝난 뒤 StringBuilder에 저장된 모든 경우의 순열을 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• 모든 경우의 순열을 구하는 permutation 함수를 만들었습니다.
• BufferedWriter에 StringBuilder에 저장된 모든 순열들을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• permutation는 result, check와 재귀를 사용하여 모든 경우의 순열을 구하도록 하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;		//1~N 범위
	public static int[] result;		//현재 경우의 순열 값
	public static boolean[] check;		//1~N 사용하였는지 확인 배열
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //--------입력값 저장-------
    	N = Integer.parseInt(br.readLine());
    	result = new int[N];
    	check = new boolean[N];
    	permutation(0);		//모든 순열 찾는 함수 실행
    	bw.write(sb.toString());	//StringBuilder에 저장된 순열들 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();

    }
    //------재귀를 통한 모든 순열의 경우를 구하는 함수------------
    public static void permutation(int length) {
    	if(length==N) {		//순열을 완성했을 때
    		for(int i=0;i<N;i++) {
    			sb.append(result[i] + " ");	//순열 값 StringBuilder에 저장
    		}
    		sb.append("\n");
    		return;
    	}
    	for(int i=1;i<=N;i++) {		//1~N 순열에 들어갈 값 탐색 및 재귀 실행
    		if(!check[i-1]) {
    			check[i-1] = true;
    			result[length] = i;
    			permutation(length+1);
    			check[i-1] = false;
    		}
    	}
    	return;
    }
}