[백준 2309번: 일곱 난쟁이][Java]

[알고리즘] 브루트 포스

 

어제 블랙잭 문제에 이어서 비슷한 일곱 난쟁이 문제를 풀어봤다.

9개의 정수를 받아, 그중 7개의 정수의 합이 100이 되면, 7개의 정수를 오름차순으로 출력하는 문제다.

 

7개의 정수를 다 더해서 100인지 확인하는 로직보다, 2개의 정수를 더한 값을 전체 합에서 뺀 케이스를 살펴보는 게 Time Complexity가 간단하겠다는 생각이 들었다.

 

2개의 정수의 합을 구하기 위해, 미리 구현해둔 permutation 메소드를 사용했다.

재귀로 이루어진 permutation 함수의 break point는 permutation의 수가 2개이며, 전체 정수에서 두 수의 합을 뺀 값이 100일 때로 설정했다.

 

위 조건을 만족하게 되면, 문제의 출력 요구조건을 맞추기 위해 sortAndPrintArr() 메소드를 호출한다.

 

sortAndPrintArr()에서 하는 작업은 아래와 같다.

1. 출력에 사용할 7개의 정수로 구성된 배열을 하나 생성한다. (아래 코드에서 rtn)

    - for 문을 돌리며 정수를 추가하되, permutation으로 부터 구한 제외할 2개의 정수는 continue로 제외

2. Arrays.sort(rtn)으로 오름차순 정렬

3. 출력

4. 문제에서 모든 정수 조합을 출력하라고 요구한 것이 아니므로, 하나의 충족 케이스만 출력하면 프로그램을 종료해야 함. 단순히 return만 호출하게 되면, 또다시 permutation함수로 코드 호출 시점이 변경되므로, main 함수 자체를 종료시킴.

 

TIL (Today I Learn)

1.  Java에서 배열 정렬

import java.util.Arrays;

Arrays.sort(arr);	// 오름차순
Arrays.sort(arr,Collections.reverseOrder());	// 내림차순

2. Main 함수 종료

System.exit(0);

3. 백준에서 제출언어를 Java8로 제출하는 게 Java11로 제출하는 것보다 빠름

    (왜 그런지는 다음에 공부해봐야겠다.. 오늘은 retrofit 공부해야지..!)

같은 코드를 다른 제출언어로(Java의 다른 버전) 제출

4. BufferedWriter와 System.out.println() 둘 다 사용해 봤는데, 코드 실행 시간은 똑같음.

   오늘 문제처럼 7개와 같이 적은 데이터를 입출력할 때에는 둘의 성능이 크게 차이 나지 않는 듯.

5. 이 글을 보고 있는 똑똑한 당신에게는 당연한 얘기일 수 있겠지만. 아래와 같이 입력 값이 한 줄에 하나로 주어질 때는 StringTokenizer를 사용하지 않는 것이 더 빠르다.

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

/* Case 1 */
value[i] = br.readline() // br의 값을 바로 변수에 할당하는 것 보다

/* Case 2 */
StringTokenizer st = new StringTokenizer(br.readline());
value[i] = Integer.parseInt(st.nextToken()); // 이렇게 하는게 더 빠름 (백준기준 4ms)

 

정답 코드

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

public class Main {
    static final int EXCLUDE_DWARF = 2;
    static int N = 9;
    static int[] index;
    static boolean[] used;
    static int[] value;
    static int total;

    static void permutation(int cnt) {
        if (cnt == EXCLUDE_DWARF) {
            int sum = value[index[0]] + value[index[1]];
            if (total - sum == 100) sortAndPrintArr();
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!used[i]) {
                used[i] = true;
                index[cnt] = i;
                permutation(cnt + 1);
                used[i] = false;
            }
        }
    }

    static void sortAndPrintArr() {
        int[] rtn = new int[7];

        int idx = 0;
        for (int j = 0; j < N; j++) {
            if (j == index[0] || j == index[1]) continue;
            rtn[idx++] = value[j];
        }

        Arrays.sort(rtn);
        for (int i = 0; i < 7; i++) {
            System.out.println(rtn[i]);
        }
        System.exit(0);
    }


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

        index = new int[EXCLUDE_DWARF];
        used = new boolean[N];
        value = new int[N];

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            value[i] = Integer.parseInt(st.nextToken());
            total += value[i];
        }

        permutation(0);
    }
}

 

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

2309번: 일곱 난쟁이