[백준] code.plus(브루트포스-순열,JAVA)6603번, 로또

문제 링크

6603번: 로또

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

 

순열이란

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

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

 

이 문제에 핵심은

1. 로또에 적을 숫자는 S의 속한 숫자이다.

2. 오름차순으로 중복되지 않는 6개의 숫자를 나열한다. = 오름차순 순열을 구해라!

 

배열

cur  : 현재 경우의 순열

 

check : 사용한 숫자 확인

 

num : 로또에 사용될 숫자

 

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

 

입력값에 따라 만들 수 있는 모든 경우의 오름차순 순열을 만들었습니다.

해당 순열들을 모두 StringBuilder에 저장하였습니다.

모든 입력이 끝난 뒤 StringBuilder에 저장된 모든 순열을 결과로 출력하였습니다.

 

문제에 해결알고리즘은

1. 첫 번째 순열에 값을 지정하고 해당 check를 true로 바꾸어주었습니다.

2. 순열의 모든 경우의 수를 구하였습니다.

3. 순열이 완성되었을 때 순열을 StringBuilder를 저장하였습니다.

4. 모든 입력에 순열을 완성한 뒤 저장하였던 StringBuilder를 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 k와 로또에 사용할 숫자 집합을 배열에 저장하였습니다.
• 모든 경우의 오름차순 순열을 구하는 lotto 함수를 만들었습니다.
• BufferedWriter에 모든 경우의 오름차순 순열을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• lotto는 num, cur, check와 재귀를 사용하여 모든 경우 오름차순 순열을 구하였습니다.
• lotto는 순열이 완성되었을 때 StringBuilder에 순열을 저장하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int K;
	public static int[] num = new int[49];	//로또에 들어갈 S집합의 수 배열
	public static int[] cur = new int[7];	//현재 순열의 값
	public static boolean[] check;		//로또 숫자 사용 확인 배열
	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
        //----------입력값 처리 및 배열 초기화---------
    	StringTokenizer st;
    	while(true) {
    		String str = br.readLine();
    		if(str.equals("0"))		//'0' 입력시 반복 종료
    			break;
    		st = new StringTokenizer(str," ");
    		K = Integer.parseInt(st.nextToken());
    		check = new boolean[K];
    		for(int i=0;i<K;i++) {
    			num[i] = Integer.parseInt(st.nextToken());
    		}
    		for(int i=0;i<K;i++) {	//로또 첫 숫자 탐색
    			check[i] = true;
    			cur[0] = num[i];
    			lotto(1,i);		//함수 실행
    			check[i] = false;
    		}
    		sb.append("\n");
    	}
    	bw.write(sb.toString());		//모든 순열 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //--------로또 모든 경우의 오름차순 순열 구하는 함수---------
    public static void lotto(int length, int min) {
    	if(length==6) {		//로또 완성시
    		for(int i=0;i<6;i++) {
    			sb.append(cur[i] + " ");
    		}
    		sb.append("\n");
    		return;
    	}
        //-------로또 각 숫자 탐색--------
    	for(int i=min;i<K;i++) {
    		if(!check[i]) {
    			check[i] = true;
    			cur[length] = num[i];
    			lotto(length+1,i);		//재귀 발동!
    			check[i] = false;
    		}
    	}
    	return;
    }
}