백준 - 로또(6603) / 조합

오늘 풀어본 문제는 ⭐로또 이다.

1. 문제 요약

• 각 줄마다 k와 k개의 수가 주어짐. 해당 주어진 수들 중 6개의 수를 선택하는 경우의 수를 모두 출력할것
• 각 케이스마다 경우의 수는 오름차순으로 출력하고, 케이스간 한 줄씩 띄어쓰기로 출력한다.

2. 알고리즘

해당 문제는 조합론 공부를 위해 풀어보았다.

이 문제의 중요점은 다음과 같다.

• 한 번 선택된 번호는 다시 뽑을 수 없다.
• 6개의 번호만을 뽑아야 한다.

처음에는 아무생각없이 순열 만드듯이 하다가 틀렸다는 걸 깨달았다.

3. 코드

어렵지 않으니 까먹을 때 마다 자주봐두자

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

public class Main {
    static int K;
    static int[] ARR;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            if (K == 0) break;

            ARR = new int[K];
            for (int i = 0; i < K; i++) ARR[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(ARR);

            johap(0, 0, new StringBuilder());
            System.out.println();
        }
    }

    static void johap(int start, int depth, StringBuilder sb) {
        if (depth == 6) {
            System.out.println(sb.toString().trim());
            return;
        }

        for (int i = start; i < K; i++) {
            int len = sb.length();
            sb.append(ARR[i]).append(' ');
            johap(i + 1, depth + 1, sb);
            sb.setLength(len); // 백트래킹(원복)
        }
    }
}

4. 알아둬야 할 점

sb.setLength(len); // 백트래킹(원복)

StringBuilder는 자주 쓰니까, 해당 함수 정도는 기억해두자!