[백준 2309/ JAVA] 일곱난쟁이

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

2309번: 일곱 난쟁이

 

간단한(?) 브루트포스 문제이다.

 

난 먼저 모든 난쟁이의 키를 합친 후 100을 뺀 값을 구했다.

그 후 두 난쟁이의 키의 합이 100에서 전체 키를 뺀 값과 같은 경우를 구했다.

 

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

public class Main {
    static int[] n = new int[9];

    public static void main(String[] args) throws IOException {
        int sum = 0, value;
        int i, j;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (i = 0; i < 9; i++) {
            n[i] = Integer.parseInt(br.readLine());
            sum += n[i]; //난쟁이 키 합
        }

        value = sum - 100; //100을 뺀 값
        Arrays.sort(n);

        for (i = 0; i < 8; i++) {
            for (j = i + 1; j < 9; j++) {
                if (i != j && (n[i] + n[j]) == value) { //난쟁이의 키의 합이 같은 경우
                    printResult(n, i, j);
                    return;
                }
            }
        }
    }
    
    //결과 출력
    public static void printResult(int[] n, int i, int j) {
        for (int p = 0; p < 9; p++) {
            if (p != i && p != j)
                System.out.println(n[p]);
        }
    }
}

 

나중에 다른 풀이를 보니 제외할 두 난쟁이의 키를 100으로 바꾸고 정렬한 후 오름차순으로 7명만 출력하는 풀이도 있었다.

이 풀이가 훨씬 효과적이다.

 

수정한 풀이

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

public class Main {
    static int[] n = new int[9];

    public static void main(String[] args) throws IOException {
        int sum = 0, value;
        int i, j;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (i = 0; i < 9; i++) {
            n[i] = Integer.parseInt(br.readLine());
            sum += n[i]; // 난쟁이 키 합
        }

        value = sum - 100; // 100을 뺀 값

        for (i = 0; i < 8; i++) {
            for (j = i + 1; j < 9; j++) {
                if (i != j && (n[i] + n[j]) == value) { // 난쟁이의 키의 합이 같은 경우
                    //제외할 두 난쟁이 키를 100
                    n[i] = 100;
                    n[j] = 100;
                    //정렬
                    Arrays.sort(n);
                    printResult(n);
                    return;
                }
            }
        }
    }

    // 결과 출력
    public static void printResult(int[] n) {
        for (int p = 0; p < 7; p++) { //7명만 출력
            System.out.println(n[p]);
        }
    }
}

 

수정한 풀이가 시간이 더 걸리는 이유는 뭘까..?