[코딩테스트 챌린지] 백준 2309 일곱 난쟁이 (java)

문제

 

문제 탐색하기

1. 일곱 난쟁이 키의 합은 100

문제를 확인해보면 9명의 난쟁이의 키를 input 값으로 받는 것을 알 수 있습니다. input 값이 많지 않으므로 정답을 도출하는 데에 전체 탐색을 해도 괜찮을 것 같다는 생각을 했습니다.

9명의 난쟁이 중 7명의 난쟁이 키의 합이 100일때의 난쟁이들의 키를 배열로 출력하면 되는데,

9명의 난쟁이에서 백설공주의 난쟁이가 아닌 2명을 제외시키는 것이 더 수월할 것으로 판단되었습니다.

 

2. 9명의 난쟁이 키의 합 구하기

7명의 난쟁이의 키를 구하기 위해서는 9명의 난쟁이 키의 합에서 2명의 난쟁이를 제외시켜 100이 나오는 경우를 구해야합니다. 즉 9명의 난쟁이 키의 합이 필요합니다. 따라서 값을 처음 입력받을 때 9명의 난쟁이 키 총합을 구하면 편리할 것으로 생각되었습니다.

 

3. 난쟁이 키를 오름차순으로 정렬하기

입력값을 배열에 저장해서 오름차순으로 정렬해서 문제 풀이를 시작하면 추후에 정렬하는 것보다 편리합니다.

java는 보편적으로 배열을 정렬할때 Arrays.sort(배열), 즉 sort() 함수를 통해서 배열을 쉽게 오름차순으로 정렬시킬 수 있으니 이를 활용하여 문제 풀이를 진행할 것입니다.

Arrays.sort() 함수는 N개의 원소를 정렬할 때 평균 O(nlog(n)) 의 시간복잡도를 가지고 최악의 경우 O(n^2)의 시간복잡도를 가지지만 N의 값이 크지 않기때문에 사용해도 될 것이라고 생각합니다.

 

따라서 정렬 및 전체탐색을 이용하여 문제를 접근하도록 하겠습니다.

 

코드 설계하기

1. 배열을 입력받습니다.
2. 9명의 난쟁이 키의 합을 변수에 저장합니다.
3. 입력받은 배열을 오름차순으로 정렬합니다.
4. 9명의 난쟁이 중 2명을 선택하는 로직을 작성합니다.
5. 제외할 2명이 정해지면 나머지 난쟁이의 키를 출력하는 함수를 생성합니다.

 

정답 코드

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

public class SevenDwarfs {

    public static void main(String[] args) throws IOException {

        // 1. 배열을 입력 받는다.
        int[] arr = new int[9];
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        int sum = 0;
        for(int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(reader.readLine());
            // 2. 9명의 난쟁이 키의 합
            sum+=arr[i];
        }

        // 3. 배열을 오름차순으로 정렬
        Arrays.sort(arr);

        // 4. 9명 난쟁이 중, 2명을 제외하는 경우의 수
        boolean chk = false;
        for(int i=0; i<arr.length; i++){
            for(int j=i; j<arr.length; j++){
                if(chk) break;
                if(sum-(arr[i]+arr[j]) == 100){
                    chk = true;
                    printResult(arr, arr[i], arr[j]);
                }
            }
        }

    }

    // #. 7 난쟁이의 키를 출력하는 함수
    private static void printResult(int[] arr, int height1, int height2) {

        for(int k = 0; k<arr.length; k++){
            if(arr[k] == height1 || arr[k] == height2){
                continue;
            }

            System.out.println(arr[k]);
        }
    }


}