중첩 반복문 대체하기

Q. 0번부터 차례대로 번호 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 구해라.

예를 들어 n이 5인 경우, 0~4까지의 원소 중 차례로 네 개를 고르므로 (0 1 2 3), (0 1 2 4), (0 1 3 4), (0 2 3 4), (1 2 3 4)의 경우가 있다.

 

A1. 반복문을 이용하는 방법

차례로 네 개를 고르므로 4중 중첩 for문을 써서 해결할 수 있다.

class Test {
    public static void main(String[] args) {
        int n = 5; // n이 5인 경우 0~4까지 원소 중 차례로 4개를 골라 출력함
        
        // 첫 번째 원소 선택
        for (int i = 0; i < n; i++) {
            // 두 번째 원소 선택 (차례대로 고르므로 첫 번째 원소보다 커야 함)
            for (int j = i + 1; j < n; j++) {
                // 세 번째 원소 선택 (차례대로 고르므로 두 번째 원소보다 커야 함)
                for (int k = j + 1; k < n; k++) {
                    // 네 번째 원소 선택 (차례대로 고르므로 세 번째 원소보다 커야 함)
                    for (int l = k + 1; l < n; l++) {
                        System.out.println("(" + i + ", " +  j  + ", " + k + ", " + l + ")");
                    }
                }
            }
        }
    }
}

 

실행결과

하지만 골라야 할 원소의 수가 늘어나면 코드가 복잡해지기 때문에 반복되는 코드를 재귀로 호출하는 방법이 더 좋은 답안이 될 것이다.

재귀로 함수를 호출하는 로직을 한 번에 떠올리기 어렵다면 이렇게 반복문으로 먼저 작성해보고, 반복되는 부분을 재귀적으로 호출하도록 변경해보는 연습을 하면 생각해내기 쉽다.

 

A2. 재귀를 이용하는 방법

차례대로 고를 숫자를 어디서부터 어디까지 고를지를 지정해서 반복, 원소 네 개를 선택하도록 재귀호출하는 방법으로 구현할 수 있다.

import java.util.*;

class Test {
    public static void main(String[] args) {
        pick(5, new ArrayList<>(), 4);
    }
    
    // n: 전체 원소 수
    // pickedList: 지금까지 고른 원소들
    // toPick: 더 고를 원소 수
    public static void pick(int n, ArrayList<Integer> pickedList, int toPick) {
        // 네 개를 모두 골랐을 경우 출력 후 재귀 탈출
        // (하지만 for문에 의해 계속 반복을 돌며 재귀함수를 탈 것)
        if (toPick == 0) {
            System.out.println(pickedList);
            return;
        }
        
        // 반복문에서 이전에 고른 숫자 +1 부터 반복을 돌았듯이
        // 직전에 고른 숫자보다 1큰 숫자부터 반복문 시작
        int startNumber = 0;
        if (pickedList.size() != 0) {
            startNumber = pickedList.get(pickedList.size() - 1) + 1;
        }
        
        for (int i = startNumber; i < n; i++) {
            pickedList.add(i);  // 작은 숫자부터 반복을 시작하여 고른 원소 리스트에 담음
            pick(n, pickedList, toPick - 1);    // 작은 원소부터 차례로 담는 과정을 재귀로 반복
            pickedList.remove(pickedList.size() - 1);   // 마지막 원소를 지우고 또 다시 추가, 재귀 반복
        }
    }
}

 

실행결과

 

 

각 파라미터의 역할

- n: 전체 원소 수 (예시 코드에서는 5개로 0~4까지의 숫자)

직전에 고른 숫자에 1을 더한 시작 원소가 1씩 커지며 반복문을 돌 때 최대 숫자를 결정한다.

n이 6일 경우 범위가 0~5까지로 늘어나 아래와 같은 결과가 나온다.

 

 

- pickedList: 지금까지 고른 원소들 목록 (예시 코드에서는 시작 시 0개, 종료 시 4개)

- toPick: 더 골라야 할 원소 수 (시작 시 4개, 종료 시 0개)

가장 작은 숫자부터 시작해 1씩 커지면서 목록에 원소가 담기고, 더 골라야 할 원소 수인 toPick이 0이 될 때 pickedList는 4가 된다.

맨 처음부터 시작해보면 아무 것도 담겨있지 않을 때 파라미터 순서로 아래와 같이 동작하며 더 골라야 할 원소 수가 0이 될 때 출력하고 중단한다.

(5, [0], 3) → (5, [0, 1], 2) → (5, [0, 1, 2], 1) → (5, [0, 1, 2], 0)

 

이후 목록에 담긴 마지막 원소를 제거하고 또 다음으로 작은 숫자를 찾는다. 마지막 원소를 지워주지 않고 해당 과정을 반복하면 아래와 같은 실행결과가 나온다.