[백준] BOJ 2309 일곱 난쟁이(Java)

1. 문제 설명

• 문제 링크: 백준 2309번 - 일곱 난쟁이
• 요약: 아홉 명의 난쟁이 중 진짜 일곱 명의 난쟁이를 찾아야 합니다. 일곱 명의 키의 합은 정확히 100입니다. 아홉 명의 키가 주어졌을 때, 진짜 일곱 명을 찾아 키를 오름차순으로 출력하는 프로그램을 작성하세요.

2. 핵심 아이디어

이 문제의 핵심은 전체 아홉 명 중 가짜 두 명을 골라내는 것입니다.

1. 발상의 전환: 아홉 명 중 일곱 명을 골라 합을 구하는 조합(Combination)을 생각할 수도 있지만, 반대로 (전체 9명의 합) - (가짜 2명의 합) = 100이 되는 두 명을 찾는 것이 훨씬 효율적입니다.
2. 전체 탐색(Brute Force): 아홉 명 중 두 명을 고르는 경우의 수는 대략 36가지(9C2) 정도로 매우 적습니다. 따라서 2중 반복문을 사용해 모든 경우를 확인해도 시간 복잡도 내에 충분히 해결 가능합니다.
3. 정렬: 출력 조건이 오름차순이므로, 탐색 전이나 후에 정렬을 수행해 줍니다.

3. 코드

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

public class Main {
    private static int[] tall;
    private static int[] fakeDwarf = new int[2]; // 가짜 난쟁이 인덱스를 저장할 배열
    private static int sum; // 아홉 난쟁이 키의 총합

    // 가짜 난쟁이 두 명을 찾는 메서드
    private static void findFakeDwarf() {
        for (int a = 0; a < 9; a++) {
            for (int b = a + 1; b < 9; b++) {
                // 전체 합에서 두 명의 키를 뺐을 때 100이 되면 정답!
                if (sum - tall[a] - tall[b] == 100) {
                    fakeDwarf[0] = a;
                    fakeDwarf[1] = b;
                    return; // 찾자마자 종료
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tall = new int[9];
        sum = 0;
        
        // 1. 입력 받기 및 전체 합 구하기
        for (int i = 0; i < 9; i++) {
            tall[i] = Integer.parseInt(br.readLine());
            sum += tall[i];
        }
        
        // 2. 오름차순 출력을 위해 미리 정렬
        Arrays.sort(tall);
        
        // 3. 가짜 난쟁이 찾기 로직 수행
        findFakeDwarf();
        
        // 4. 결과 출력 (가짜 두 명을 제외한 나머지 출력)
        for (int i = 0; i < 9; i++) {
            if (i != fakeDwarf[0] && i != fakeDwarf[1]) {
                System.out.println(tall[i]);
            }
        }
    }
}

4. 코드 포인트 해설

• sum - tall[a] - tall[b] == 100: 이 문제의 가장 핵심적인 로직입니다. 7명을 더하는 것보다 전체에서 2명을 빼는 방식이 코드가 간결하고 직관적입니다.
• Arrays.sort(tall): 정답 출력 시 오름차순으로 보여줘야 하므로, 탐색 전에 미리 정렬을 해두면 출력할 때 순서대로 출력하기만 하면 되어 편리합니다.
• Early Return: findFakeDwarf() 메서드에서 정답을 찾자마자 return을 사용해 불필요한 반복을 방지했습니다. 문제에서 가능한 정답이 여러 개일 경우 아무거나 하나만 출력하라고 했기 때문에 효율적인 처리가 가능합니다.

5. 시간 복잡도 분석

• 입력 및 합계 계산: $O(9)$
• 정렬: $O(9 \log 9)$
• 이중 루프(가짜 찾기): $O(9 \times 8 / 2) = 36$번 연산
• 최종 출력: $O(9)$

데이터의 개수가 9개로 고정되어 있어 시간 복잡도는 사실상 상수 시간($O(1)$)에 가깝습니다. 브루트포스 알고리즘의 전형적인 예시라고 할 수 있습니다.

6. 마치며

이번 문제는 전체 경우의 수가 적을 때 사용할 수 있는 완전 탐색 기법을 익히기에 좋은 문제였습니다. 특히 "7명을 찾기 위해 2명을 버린다"는 역발상이 구현을 훨씬 단순하게 만들어 주었습니다.

대회였다면 언어를 cpp로 바꿔서 next_permutation을 사용했겠지만 java는 next_permutation이 메모리 구조적 문제로 없다보니 이렇게 구현을 해봤습니다.