Q 2309 일곱 난쟁이

💡 문제 요약 및 분석

주어진 9명의 난쟁이들 중 7명 키의 합산이 100이 되는 조합을 찾아서 오름차순으로 정렬한다.

💡 알고리즘 설계

✅ 핵심 아이디어 : 9명 키의 총합 - 난쟁이[i] - 난쟁이[j] == 100 인 조합을 찾자.

1. 입력

   • 표준입력을 받아 9칸짜리 배열에 저장한다.
   • total 변수에 키의 총합을 저장한다.

2. 연산

   • 이중for문으로 (total - dwarf[i] - dwarf[j] == 100) 인 조합을 찾는다.
   • true 면 해당 i, j 값을 0으로 설정하고 break;

3. 출력

   • dwarf 배열을 오름차순으로 정렬한 후 출력한다.

💡 코드

import java.util.*;

public class Main {

    static int read() throws Exception {
        int n = 0, c = 0;
        while((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int[] dwarfs = new int[9];
        int total = 0;
        for (int i = 0; i < 9; i++) {
            dwarfs[i] = read();
            total += dwarfs[i];
        }

        Loop:
        for (int i = 0; i < 8; i++) {
            for (int j = 1; j < 9; j++) {
                if (total - dwarfs[i] - dwarfs[j] == 100) {
                    dwarfs[i] = 0;
                    dwarfs[j] = 0;
                    break Loop;
                }
            }
        }

        Arrays.sort(dwarfs);
        for (int i = 2; i < 9; i++) {
            System.out.println(dwarfs[i]);
        }
    }

}

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

시간 복잡도	공간 복잡도
O(1)	O(1)