[백트래킹/자바] 코드트리 IL. 특정 조건에 맞게 k개 중에 1개를 n번 뽑기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

위 문제는 k<= 4, n<=8 이므로 완전탐색이 웬만해선 가능한 문제이며, 조건에 맞는 숫자 조합을 골라서 출력하는 문제이므로, 백트래킹을 사용하면 된다.

 

문제 풀이

간단한 문제라 설명은 생략한다.

package 코드트리.완전탐색.백트래킹;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 특정조건에맞게_k개중에1개를_n번뽑기 {
    private static List<Integer> li = new ArrayList<>();
    private static int n, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        k = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        go();
    }

    public static void go() {
        if (li.size() == n) {
            printNumbers();
            return;
        }
        for (int i = 1; i <= k; i++) {
            if (li.size() < 2 || !isDuplicate(i)) {
                li.add(i);
                go();
                li.remove(li.size() - 1);
            }
        }
    }

    private static boolean isDuplicate(int i) {
        return li.size() >= 2 && li.get(li.size() - 2) == li.get(li.size() - 1) && li.get(li.size() - 1) == i;
    }

    private static void printNumbers() {
        for (Integer i : li) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}