Q 2309 일곱 난쟁이

💡 문제 요약 및 분석

일곱 난쟁이의 키의 합계는 100이다. 아홉 난쟁이들 중에서 키의 합이 100이 되는 조합을 하나만 찾아서 출력하면 된다.

💡 알고리즘 설계

이번에는 배열이 필요할 것 같다. 9칸짜리 배열에 난쟁이들의 키를 입력받는다. 중첩 for문을 돌면서 배열 중 2개의 값을 빼고 나머지 값을 더한다. (이렇게 하면 모든 경우의 수를 돌아볼 수 있다) 합계가 100인 조합을 찾아내면 2개 값을 remove 하고 배열을 오름차순 정렬한 후 출력하면 된다.

💡 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            list.add(sc.nextInt());
        }

        // 배열 돌면서 2개 값을 제외한 나머지를 더한 값이 100인 경우 찾기
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                for (int k = 0; k < list.size(); k++) {
                    if (k != i && k != j) {
                        sum += list.get(k);
                    }
                }
                if (sum == 100) {
                    List<Integer> result = new ArrayList<>();
                    for (int k = 0; k < list.size(); k++) {
                        if (k != i && k != j) {
                            result.add(list.get(k));
                        }
                    }
                    // 오름차순 정렬 후 출력
                    result.stream()
                            .sorted()
                            .forEach(System.out::println);
                    return;
                } else {
                    sum = 0;
                }
            }
        }
    }
}

💡 틀린 부분 수정

💡 시간 복잡도, 공간 복잡도

시간 복잡도공간 복잡도
O(n^3)O(n)

  • ⏱️ 이중 루프, 내부 루프가 총 3개 있어서 일반화하면 O(n^3) 이지만, n = 9 이므로 실제 속도는 매우 빠르다.

  • 🧠 입력 크기에 비례하는 리스트가 있어서 공간 복잡도는 O(n) 이다.

💡 다른 풀이

지금까지는 편의상 Scanner 를 사용했지만 코테에서는 문제 풀이 속도가 미션으로 주어지는 경우도 있기에 BufferedReader 로 바꿔서 작성했다. 그리고 기존 작성한 코드가 너무 중첩문 범벅이라 좀더 단순화할 방법이 없는지 찾아보았는데 조금 더 간단한 방법의 풀이가 있어 구현해보았다. 코드가 간결해졌고 속도도 훨씬 빨라진 것을 볼 수 있다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] ary = new int[9];

        // 키를 입력받음과 동시에 전체 키를 더해둔다.
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            ary[i] = Integer.parseInt(br.readLine());
            sum += ary[i];
        }

        br.close();

        // 아홉 난쟁이 배열의 합계에서 2개를 뺀 값이 100이 되는 경우의 수를 찾는다.
        for (int i = 0; i < ary.length; i++) {
            for (int j = i + 1; j < ary.length; j++) {
                if (sum - ary[i] - ary[j] == 100) {
                    ary[i] = 0;
                    ary[j] = 0;

                    // 오름차순 정렬 후 출력
                    Arrays.sort(ary);
                    for (int k = 2; k < ary.length; k++) {
                        System.out.println(ary[k]);
                    }
                    return;
                }
            }
        }
    }
}

💡 느낀점 및 기억할 정보

BufferedReader

Scanner 는 키보드의 키를 누르는 즉시 프로그램에 전달되지만 Buffer 를 사용하면 입력된 값을 모아다가 개행 문자를 입력하거나 버퍼가 가득 차면 프로그램에 전달한다. 때문에 Scanner 보다 빠른 속도가 강점이다. 입력은 readLine() 메서드로 이루어지는데, 이 때 리턴값은 String 이다. 그래서 형변환을 해주거나 StringTokenizer, split 등을 사용해야 한다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int i = Integer.parseInt(br.readLine());

// StringTokenizer 를 사용하면 공백 단위로 자를 수 있다.
StringTokenizer st = new StringTokenizer(br.readLine());
int a = Interger.parseInt(st.nextToken());
int b = Interger.parseInt(st.nextToken());

BufferedWriter

일반적으로 출력을 할 때는 System.out.print 를 사용하지만 많은 양의 출력이 필요한 경우 버퍼를 사용하는 것이 좋다.

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String str = "출력할 문자열";
bw.write(str); // 출력
bw.newLine(); // 줄바꿈
bw.flush(); // 남아있는 데이터 전부 출력
bw.close();