☆[백트래킹/자바] 코드트리 IL. k개 중에 1개를 n번 뽑기

문제

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

 

분석

주어진 조건에 맞춰 경우의 수를 출력하는 문제입니다.

 

우리가 알고있는 순열/조합의 경우 구현되어있는 라이브러리를 사용하는 것 외에, 일반적으로는 for문을 이용한 완전탐색을 이용하여 모든 경우의 수를 구하는 접근법을 쉽게 떠올릴 수 있습니다.

 

하지만 이 문제에서는 주어지는 자릿수가 매번 바뀌며, 입력하는 숫자도 조합을 이용하여 입력되어야 하므로 단순하게 for문만을 사용한 완탐으로 접근한다면 까다로울 수 있습니다. 이처럼 for문으로 처리하기 어려운 순열/조합과 같은 경우의 수를 구하는 완전 탐색 방법으로 백트래킹이 있습니다.

 

백트래킹은 일반적으로 재귀함수를 이용하여 순열/조합을 구할 때 사용되는 알고리즘 기법입니다.

 

여기서도 백트래킹을 이용하면 간단한 로직으로 문제를 풀어낼 수 있습니다.

 

풀이

package 코드트리.백트래킹;

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

public class Main {
    private static int n, k;
    private static List<Integer> li = new ArrayList<>();
    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());
        choose(1);
    }

    private static void choose(int x) {
        if (x == n + 1) {
            print();
            return;
        }
        x++;
        for (int i = 1; i <= k; i++) {
            li.add(i);
            choose(x);
            li.remove(li.size() - 1); // 중요한 포인트
        }
    }
    private static void print() {
        li.forEach(o -> System.out.print(o + " "));
        System.out.println();
    }

}

여기서 주의할 점은, 모든 경우의 조합을 탐색하기 위해서는 li.add() 이후에 재귀함수를 실행한 뒤, 해당 자릿수에 대한 다른 경우를 계산할 수 있도록 li.remove() 처리를 해 줘야 한다는 것입니다. 이 외에는 단순한 로직이라 설명은 생략하겠습니다.