[JAVA_백준 2309] 일곱 난쟁이

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

 

 

📌 문제 탐색하기

9명의 난쟁이의 키의 값중에서 7명의 키의 합이 정확하게 100이 되는 경우를 찾아야하는 문제이다. 

선택된 7명의 난쟁이의 키를 오름차순으로 출력해야한다. 

 

가능한 시간복잡도

1. 정렬을 사용하니까 O(log n)
2. 2명 제외하도록 경우의 수 찾아야하니까 O(n^2)  

---

📌 코드 설계하기

1. 9명의 난쟁이의 키를 입력받습니다.
2. 난쟁이들의 키를 오름차순으로 정렬합니다.
3. 9명의 키의 합을 구하고 이중 반복문을 사용해서 두명의 난쟁이를 선택하고 전체 합에서 두명의 키를 뺀 값이 100이 되는 경우를  찾습니다. 만족하는 경우를 찾으면 반복문 종료하면 됩니다.
4. 2명 제외한 7명 키를 오름차순으로 정렬해서 출력하면 됩니다. 

---

📌 정답 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] height = new int[9];
        int total = 0;

        for (int i = 0; i < 9; i++) {
            height[i] = sc.nextInt();
            total += height[i];
        }

        Arrays.sort(height);

        int exclude1 = -1, exclude2 = -1;
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                if (total - height[i] - height[j] == 100) {
                    exclude1 = i;
                    exclude2 = j;
                    break;
                }
            }
            if (exclude1 != -1) break;
        }

        for (int i = 0; i < 9; i++) {
            if (i != exclude1 && i != exclude2) {
                System.out.println(height[i]);
            }
        }
    }
}