문제
9명의 난쟁이 중에서 키의 합이 100이 되는 7명을 찾아 키를 오름차순으로 출력하는 문제이다. 답이 유일하게 존재함이 보장되며 스페셜 저지 문제이다.
입력
아홉 줄에 걸쳐 9명의 난쟁이의 키가 주어진다. 키는 100 이하의 자연수이며, 중복되지 않는다.
출력
일곱 난쟁이의 키를 오름차순으로 한 줄에 하나씩 출력한다.
예제
| 입력 | 출력 |
|---|---|
20 7 23 19 10 15 25 30 9 | 7 9 10 19 20 23 25 |
풀이
역발상 브루트포스를 사용한다. 7명을 직접 고르는 대신, 9명 중 합이 100이 아닌 2명을 찾아 제거한다. 9명의 합에서 100을 뺀 값과 같은 두 수를 찾으면 된다.
- 9개의 키를 입력받아 배열에 저장하고 버블 정렬로 오름차순 정렬한다.
- 9명의 키 합계(
sum9)를 구하고num = sum9 - 100을 계산한다. - 이중 루프로
arr[i] + arr[j] == num을 만족하는 인덱스 쌍 (i, j)를 탐색한다. - 해당 인덱스 두 개를 제외하고 나머지 7개의 값을 순서대로 출력한다.
핵심 아이디어: 7명을 C(9,7) = 36가지로 직접 고르는 대신, 제거할 2명을 C(9,2) = 36가지로 탐색한다. 정렬 후 역발상으로 접근하면 구현이 훨씬 단순해진다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Day02BOJ2309specialJudge일곱난쟁이 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
;
int[] arr = new int[9];
for (int i = 0; i < 9; i++)
arr[i] = Integer.parseInt(br.readLine());
// 거꾸로 해봅시다.
int sum9 = 0;
for (int i = 0; i < 9; i++) {
sum9 += arr[i];
}
bubbleSort(arr);
int num = sum9 - 100;
int idx1 = 0;
int idx2 = 0;
outer: for (int i = 0; i < 8; i++) {
for (int j = i + 1; j < 9; j++) {
if (arr[i] + arr[j] == num) {
idx1 = i;
idx2 = j;
break outer;
}
}
}
for (int i = 0; i < 9; i++) {
if (i != idx1 && i != idx2)
System.out.println(arr[i]);
}
br.close();
}
private static void bubbleSort(int[] arr) {
for (int i = 8; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}복잡도
- 시간: O(1) — 입력 크기가 9로 고정. 버블 정렬과 이중 루프 모두 상수 시간
- 공간: O(1) — 크기 9의 고정 배열