728x90
반응형
1. 문제 설명
- 문제 링크: 백준 2309번 - 일곱 난쟁이
- 요약: 아홉 명의 난쟁이 중 진짜 일곱 명의 난쟁이를 찾아야 합니다. 일곱 명의 키의 합은 정확히 100입니다. 아홉 명의 키가 주어졌을 때, 진짜 일곱 명을 찾아 키를 오름차순으로 출력하는 프로그램을 작성하세요.
2. 핵심 아이디어
이 문제의 핵심은 전체 아홉 명 중 가짜 두 명을 골라내는 것입니다.
- 발상의 전환: 아홉 명 중 일곱 명을 골라 합을 구하는 조합(Combination)을 생각할 수도 있지만, 반대로 (전체 9명의 합) - (가짜 2명의 합) = 100이 되는 두 명을 찾는 것이 훨씬 효율적입니다.
- 전체 탐색(Brute Force): 아홉 명 중 두 명을 고르는 경우의 수는 대략 36가지(9C2) 정도로 매우 적습니다. 따라서 2중 반복문을 사용해 모든 경우를 확인해도 시간 복잡도 내에 충분히 해결 가능합니다.
- 정렬: 출력 조건이 오름차순이므로, 탐색 전이나 후에 정렬을 수행해 줍니다.
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이 메모리 구조적 문제로 없다보니 이렇게 구현을 해봤습니다.
728x90
반응형
'Algorithm' 카테고리의 다른 글
| [백준] BOJ 2979 트럭 주차(Java) (0) | 2026.03.14 |
|---|---|
| [백준] BOJ 10808 알파벳 개수(Java) (0) | 2026.03.13 |
| [LeetCode] 427 Construct Quad Tree (1) | 2025.07.07 |
| [백준] BOJ 1655 가운데를 말해요(CPP) (0) | 2023.05.25 |
| [백준] BOJ 10026 적록색약(CPP) (0) | 2023.05.24 |