[Baekjoon(JAVA) - Algorithm] 2309번: 일곱 난쟁이 (브루트포스 알고리즘)

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

---

 

Answer 1

import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        final int DWARF_COUNT = 9;
        final int DWARF_COUNT_TO_EXCLUDE = 2;
        int[] dwarfHeights = new int[DWARF_COUNT];
        int dwarfHeightSum = 0;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int dwarfHeight = 0;
            for (int i = 0; i < dwarfHeights.length; i++) {
                dwarfHeight = Integer.parseInt(br.readLine());
                dwarfHeights[i] = dwarfHeight;
                dwarfHeightSum += dwarfHeight;
            }
        } catch (IOException e) {
            System.err.println("ERROR = " + e.getMessage());
        }

        for (int i = 0; i < dwarfHeights.length - 1; i++) {
            for (int j = i + 1; j < dwarfHeights.length; j++) {
                if (dwarfHeightSum - dwarfHeights[i] - dwarfHeights[j] == 100) {
                    dwarfHeights[i] = 0;
                    dwarfHeights[j] = 0;
                    break;
                }
            }
            if (dwarfHeights[i] == 0) {
                break;
            }
        }

        Arrays.sort(dwarfHeights);
        for (int i = DWARF_COUNT_TO_EXCLUDE; i < dwarfHeights.length; i++) {
            System.out.println(dwarfHeights[i]);
        }
    }
}

 

Code Review

final int DWARF_COUNT = 9;
final int DWARF_COUNT_TO_EXCLUDE = 2;
int[] dwarfHeights = new int[DWARF_COUNT];
int dwarfHeightSum = 0;

지문에서 주어진 난쟁이 아홉 명을 `DWARF_COUNT`로 선언했다.

일곱 난쟁이를 제외한 두 난쟁이를 `DWARF_COUNT_TO_EXCLUDE`로 선언했다.

1 ~ 7명까지의 난쟁이를 구하는 것보다
9명에서 2명의 난쟁이를 빼는 것이 더 효율적이다.

 

9명의 난쟁이를 위한 배열 `dwarfHeights`을 생성한다. 이때 배열의 크기는 위에서 선언한 `DWARF_COUNT` 9이다.

9명의 난쟁이 키를 모두 더할 변수 `dwarfHegihtSum`을 선언한다.

 

try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
    ...
} catch (IOException e) {
    System.err.println("ERROR = " + e.getMessage());
}

`try-with-resources`로 try에 객체의 자원을 받고, try문이 종료되면 그 자원을 자동으로 반환한다.

`System.in`으로 사용자로부터 입력받은 데이터를 바이트 스트림으로 받는다.

`InputStreamReader` 클래스로 바이트 스트림을 문자 기반 스트림으로 변환한다.

`BufferedReader` 클래스로 문자 스트림을 읽는다.

 

아래는 try문 안의 로직이다.

int dwarfHeight = 0;
for (int i = 0; i < dwarfHeights.length; i++) {
    dwarfHeight = Integer.parseInt(br.readLine());
    dwarfHeights[i] = dwarfHeight;
    dwarfHeightSum += dwarfHeight;
}

for문에서 난쟁이 키를 구하는 `dwarfHeight`를 선언한다.

for문은 `dwarfHeights`배열의 길이 9만큼 반복한다.

`dwarfHeight`에는 입력받은 문자열 `br.readList()`을 `Integer.parseInt()` 메서드로 정수 변환한 값을 대입한다.

`dwarfHeights` 배열에 차례대로 `dwarfHegiht`를 넣는다.

모든 난쟁이의 키를 더한 값이 `dwarfHegihtSum`이 될 것이다.

`dwarfHeightSum += dwarfHeight`은 `dwarfHeightSum = dwarfHeightSum + dwarfHeight`와 같다.

 

for (int i = 0; i < dwarfHeights.length - 1; i++) {
    for (int j = i + 1; j < dwarfHeights.length; j++) {
        if (dwarfHeightSum - dwarfHeights[i] - dwarfHeights[j] == 100) {
            dwarfHeights[i] = 0;
            dwarfHeights[j] = 0;
            break;
        }
    }
    if (dwarfHeights[i] == 0) {
        break;
    }
}

난쟁이 9명에서 7명의 키가 100임을 구해야 된다.

난쟁이 7명의 키가 100이고 나머지 2명을 각각 A, B라고 했을 때

100 + A + B = `dwarfHeightSum`. 즉, 난쟁이 9명의 총합이다.

따라서 `dwarfHeightSum - A - B`처럼 총합에서 A, B를 빼면 100이 나오는 식으로 구하면 된다.

 

첫 번째 for문은 `i`를 0에서 전체 난쟁이 인원 - 1 까지, 두 번째 for문은 `i + 1`부터 전체 난쟁이 인원까지 반복한다.

 

`dwarfHeightSum - dwarfHeights[i] - dwarfHeights[j] == 100`이 true가 되면

dwarfHeights[i], dwarfHeights[j] 각 난쟁이를 0으로 초기화해준다.

이후 for문을 `break`로 벗어난다.

 

Arrays.sort(dwarfHeights);
for (int i = DWARF_COUNT_TO_EXCLUDE; i < dwarfHeights.length; i++) {
    System.out.println(dwarfHeights[i]);
}

이때 `dwarfHeights` 난쟁이 배열에서 두 칸이 0이다.

 

`Arrays.sort()` 메서드로 배열을 오름차순으로 정렬한다.

이렇게 되면 0이 배열 index 기준 0, 1에 정렬되어 있으므로 for문을 index 2부터 9까지 반복해서 출력하면 된다.

 

Result

처음 이 문제를 풀 때 브루트포스 알고리즘이다 보니 처음부터 끝까지 더하는 식으로 구하면 될 것 같았다.

계속 고민하면서 풀고 있으니 시간이 너무 많이 흘러서 결국 방법을 찾아봤다.

거꾸로 생각하면 쉬운 문제였는데 처음에 문제를 너무 직역해서 풀려고 한 거 같다. (창의성이 필요한 것 같다..)