BOJ 6603 로또

문제출저

풀이

개인적으로 제일 취약한 유형인 백트래킹 문제이다.
백트래킹 문제는 Recursion(재귀)의 개념이 포함된다.

  • Recursion : 자기 자신을 호출하는 함수

재귀함수를 작성할때는 재귀함수가 종료되는 시점을 정해주는것이 중요하다!

가령 1, 2, 3, 4, 5 중에서 3개의 수를 뽑아서 (중복없이) 출력한다고 할때,
3개의 수를 뽑는 것을 재귀함수로 만든다면, 재귀 함수가 종료되는 시점은 당연히 3개의 수를 다 뽑았을때이다.
첫번째 수로 1을 뽑았다고 하게되면,
두번째 수로 올 수 있는 수들은 2, 3, 4, 5가 된다.
즉, 첫번재 수가 i라고 할경우 두번째 자리에 올 수있는 수는 i+k ( 1<= k < n (n = 5))가 된다.
두번째 수가 2로 정해지게 됬다면,
세번째 수로 올 수 있는 수들은 3, 4, 5가 될 것이다.
1, 2, 3 을 출력하게 된다면
목표로 하는 3개의 수를 뽑는것이 완료되었으므로 현재까지 뽑는 숫자를 출력해준 다음,
그 다음 선택지인 4, 5를 고려해주게 된다.
마지막 자리에 있는 3을 빼주고 그 다음 차례인 4를 넣어주고 1, 2, 4 를 출력하고 그 다음 또다시 마지막 자리에 있는 4를 빼주고 5를 넣어 1, 2, 5를 출력한다.

즉, 현재위치에서 숫자를 하나씩 담고 다음 위치로 넘어가서 숫자를 하나씩 담아준 다음에
담은 숫자들이 6개가 되는지 확인해주고, 6개라면 담은 숫자들을 출력하고,
숫자들 중 하나를 제거하여 아직 담지 못한 숫자들을 담는 방식을 통해 문제를 해결할 수 있다.
숫자를 담는데는 List 자료구조를 이용하였다.

소스코드

전체소스

List<Integer> selectedNumList = new ArrayList<>();
  
public void selectNums(int idx, int k) {
    if(selectedNumList.size() == 6) {   // 종료조건
    	for(int num : selectedNumList) {
        	System.out.print(num);
        }
        System.out.println();
    }	
    
    for(int i = idx; i< k; i++) {
    	selectedNumList.add(numList.get(i)); // 현재 위치에서 숫자를 담음
        selectNum(i + 1, k);  // 다음번에 담을 수 있는 수를 탐색
        selectNumList.remove(numList.get(i)); // 현재 담은 숫자를 제거(다음 후보 숫자 탐색을 위해)
    }
}