백준 6603(로또) - Python(파이썬),Java(자바)- 백트래킹

6603번: 로또

 

파이썬 Permutation: https://coooco.tistory.com/72

📌 파이썬 Combination 사용 

import sys
from itertools import combinations
#0이 입력되기 전까지 계속 입력받기
while True:
    s = list(map(int,sys.stdin.readline().split()))
    #로또 종류 개수
    k = s.pop(0)
    #로또 개수 0이면 그만 입력받기
    if k==0:
        break
    #오름차순으로 정렬
    s.sort()
    #s개의 수 중에 6개 고르기
    nC6 = combinations(s,6)
    #리스트로 입력받아서 string
    for i in nC6:
        print(" ".join(str(j) for j in i))
    print()

📌 Combination 사용하지 않고 백트래킹

이거의 원리 ->

comb([0,1,2,3],2)

= { 0을 고른 상태에서 comb([1,2,3],1) }+ { 1을 고른 상태에서 comb([2,3],1) } +{ 2를 고른 상태에서 comb( [3],1 ) }

=

{ 0을 고른 상태에서 1을 고르기 } + { 0을 고른 상태에서 2 고르기 } +{ 0을 고른 상태에서 3 고르기 } 

+ { 1을 고른 상태에서 2 고르기 } + { 1을 고른 상태에서 3 고르기}

+ { 2를 고른 상태에서 3고르기 }

 

즉 , comb 함수에는 ( 골라야하는 배열, 배열에서 골라야하는 갯수 )를 변수로 가진다.

💻 Python(파이썬)

import sys

def comb(arr,n):
	#종류 담는 리스트 
    result=[]
    #뽑을 애가 없는 경우
    if n==0:
        return [[]]
    #i:인덱스, num:배열 안에 있는 번호
    for (i,num) in enumerate(arr):
    	#재귀함수 : i번째를 택했을 때 
        for j in comb(arr[i+1:],n-1):
            result.append([num]+j)
    return result

while True:
    s = list(map(int,sys.stdin.readline().split()))
    k = s.pop(0)
    if k==0:
        break
    s.sort()
    result = comb(s,6)
    for i in result:
        print(" ".join(str(j) for j in i))
    print()

💻Java(자바)

import java.util.*;
import java.io.*;

public class Main {
    static boolean [] chk;
    static int[] s;
    static int k;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true){
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            k = Integer.parseInt(st.nextToken());
            s = new int[k];
            chk = new boolean[k];
            if(k==0){
                break;
            }
            for(int i=0;i<k;i++){
                s[i]=Integer.parseInt(st.nextToken());
            }
            Arrays.sort(s);
            dfs(0,0);
            System.out.println();
        }
    }
    public static void dfs(int depth,int start){
        if(depth==6){
            for(int i=0;i<k;i++){
                if(chk[i]){
                    System.out.print(s[i]+" ");
                }
            }
            System.out.println();
        }
        for(int i=start;i<k;i++){
            chk[i]=true;
            dfs(depth+1,i+1);
            chk[i]=false;
        }
    }
}