JAVA 백준 문제풀이 (25) 2309: 일곱 난쟁이

 

가짜 난쟁이를 찾아내는 문제인데 <스페셜 저지>라는 문구가 눈에 띈다.

정답이 여러가지가 나올 수 있으며 무엇이 됐든 정답이면 통과할 수 있다는 의미이다.

 

상식적으로 생각해봐도 난쟁이들의 키의 합이 100이라는 사실만으로 걸러낸다면 진짜 난쟁이가 걸러질 수도 있겠다.

대다수의 저난이도 문제들이 그렇듯 복잡한 알고리즘이 필요한 문제는 아니지만 동일한 유형의 접해본 적이 없다면 헤맬 수도 있다.

 

힌트를 줄테니 바로 풀어보자. 주어지는 값으로 합을 구하려하지 말고 합에서 주어지는 값을 빼는 건 어떨까?

10분 고민해보고 답이 안나오면 밑으로 내려가자.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

    static int dwarfs[] = new int[9];
    public static void main(String[] args) throws IOException {
        inputDwarfsList();

        Arrays.sort(dwarfs);
        int dwarfs_length = Arrays.stream(dwarfs).sum();

        findingFakeDwarfs(dwarfs, dwarfs_length);
        printDwarfsList(dwarfs);
    }

 

코드는 해당 순서로 진행될 것이다.

1. 입력값으로 배열을 만든다.

2. 정렬

3. 난쟁이 키의 합을 구한다. 

( 정렬과 합을 구하는 부분은 그냥 내장 API로 대체했다 )

4. 가짜 난쟁이를 찾는다.

5. 난쟁이 목록을 출력한다.

 

 

 

 

1. 입력값 배열 생성

private static void inputDwarfsList() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    for (int i=0; i<9; i++) {
        dwarfs[i] = Integer.parseInt(br.readLine());
    }
}

2. 정렬

3. 합

4. 가짜 난쟁이 찾기

private static void findingFakeDwarfs(int[] dwarfs, int dwarfs_length) {
    outer : for (int i = 0; i< dwarfs.length; i++) {
        for (int j = 0; j< dwarfs.length; j++) {
            if ( i == j ) { continue; }
            int sum = dwarfs[i] + dwarfs[j];
            if ( dwarfs_length - sum == 100) {
                dwarfs[i] = 0;
                dwarfs[j] = 0;
                break outer;
            }
        }
    }
}

모든 난쟁이의 키 합이 100이기 때문에 임의 난쟁이 둘의 키를 뺐을 때 100이 나온다면 나머지 난쟁이는 진짜 난쟁이가 된다.

break으로 쓸데없는 연산을 줄였다.

 

5. 난쟁이 리스트 출력

private static void printDwarfsList(int[] dwarfs) {
    for (int n : dwarfs) {
        if ( n != 0 ) {
            System.out.println(n);
        }
    }
}