백준 2309번. 일곱 난쟁이 (Java)

Problem

• 문제 링크

일곱 난쟁이의 키가 주어졌을 때 합이 100 이 되도록 하는 일곱 난쟁이의 키를 출력하는 문제입니다.

Solution

문제를 살펴보면 일곱명의 합을 전부 다 구해봐야 할 것 같지만 사실은 두명만 구하면 됩니다.

주어진 난쟁이는 9명, 실제 난쟁이는 7명입니다.

9명 중에서 2명의 키를 뺀 값이 100이기 때문에

2명의 합 = 9명의 합 - 100

위 식을 이루는 2명을 구하면 됩니다.

2명의 합을 O(n) 에 구하는 방법은 정렬 후에 양 끝 인덱스부터 차례로 합을 구해서 비교하면 됩니다.

두 값의 합이 target 보다 작다면 왼쪽 인덱스를 하나 증가시키고, target 보다 크다면 오른쪽 인덱스를 하나 감소시킵니다.

Java Code

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int[] height = new int[9];
        int sum = 0;

        for (int i=0; i<9; i++) {
            int input = Integer.parseInt(br.readLine());
            height[i] = input;
            sum += input;
        }

        Arrays.sort(height);

        eraseTwoHeight(height, sum - 100);

        for (int i=0; i<9; i++) {
            if (height[i] != 0) {
                bw.write(height[i] + "\n");
            }
        }
        bw.flush();
    }

    static void eraseTwoHeight(int[] arr, int target) {
        int left = 0;
        int right = 8;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                arr[left] = 0;
                arr[right] = 0;
                return;
            }
            
            if (sum > target) {
                right--;
            } else {
                left++;
            }
        }
    }
}