[백준/JAVA] 6603번: 로또

🔺 문제

6603번: 로또

 

 

 

🔺 코드

- 1) depth가 6일 때, check[i]가 true인 경우에만 출력

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A;
    static boolean[] check;
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true) {
            String str = br.readLine();
            
            if(str.equals("0")) {
                System.out.println(sb);
                break;
            }
            
            // 초기값 세팅
            String[] input = str.split(" ");
            N = Integer.parseInt(input[0]);
            A = new int[N];
            check = new boolean[N];
            
            for(int i = 0 ; i < N ; i++) {
                A[i] = Integer.parseInt(input[i + 1]);
            }
            
            back(0, 0);
            sb.append("\n");
        }
    }
    
    private static void back(int startIdx, int depth) {
        if(depth == 6) {
            for(int i = 0 ; i < N ; i++) {
                if(check[i]) { // 🔔 check 배열의 값이 true인 값만 출력
                    sb.append(A[i]).append(" ");
                }
            }
            sb.append("\n");
        }
        
        for(int i = startIdx ; i < N ; i++) {
            check[i] = true;
            back(i + 1 , depth + 1); // 본인 제외하고 다음 수로 넘어가게 i + 1
            check[i] = false;
        }
    }
}

 

 

- 2) 결과 배열 result를 따로 만들어서 출력에 이용

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] A, result;
    static boolean[] check;
    
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        while(true) {
            String str = br.readLine();
            
            if(str.equals("0")) {
                System.out.println(sb);
                break;
            }
            
            // 초기값 세팅
            String[] input = str.split(" ");
            N = Integer.parseInt(input[0]);
 
            A = new int[N];
           result = new int[N];
            check = new boolean[N];
            
            for(int i = 0 ; i < N ; i++) {
                A[i] = Integer.parseInt(input[i + 1]);
            }
            
            back(0, 0);
            sb.append("\n");
        }
    }
    
    private static void back(int startIdx, int depth) {
        if(depth == 6) {
            for(int i = 0 ; i < 6 ; i++)    sb.append(result[i]).append(" ");
            sb.append("\n");
        }
        
        for(int i = startIdx ; i < N ; i++) {
            if(!check[i]) {
               result[depth] = A[i]; // 결과 배열 갱신
                
                check[i] = true;
                back(i, depth + 1);
                check[i] = false;
            }
        }
    }
}

 

 

✅ 해결 아이디어
✔ 백트래킹
- 종료 조건 : depth가 6일 때 결과 배열 출력
- 종료 조건 아닌 반복문
  └ check 배열 사용 ; 중복된 수가 들어오지 못 하도록 
  └ startIdx부터 시작 ; 순열 아닌 조합!

 

---

💬 느낀 점

감이 잡힌 거 같은데

한 끗 차이로(?) 자꾸 정답을 비껴나가고... 그랬다...

한 줄 한 줄 왜 필요한지 생각하면서 잘 작성해보좌,,,

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[알고리즘] 백준 6603번 로또 Java

 

[백준] 6603번 로또 - Java, 자바