[백준] 2309번 - 일곱 난쟁이

문제 링크 : https://www.acmicpc.net/problem/2309

문제 탐색하기

1) 문제 분석

총 9명의 난쟁이 키가 주어짐
이 중 7명을 뽑아서 합이 100이 되는 경우를 찾기
즉, 9명 중 2명을 제거했을 때 나머지 7명의 합이 100이 되는지 검사

2) 가능한 시간복잡도

(1) 이중 루프 (i, j)

9명 중 2명을 고르는 경우:(92)=9×82=36가지 조합(29)=29×8=36가지 조합

(2) 각 루프 안에서 수행되는 연산

filter() 연산 → O(9)
for-of 합산 → O(7) (정확히는 O(9 - 2))
총 O(9 + 7) ≈ O(16) ≈ O(n), 단일 루프 내부 비용

(3) 전체 시간 복잡도

O(36)×O(n)=O(n2)O(36)×O(n)=O(n2)
-> 여기서 n = 9 고정이므로, 실제로는 O(81) = 매우 작음

3) 알고리즘 선택

: 경우의 수가 적고, 각 조합 처리 비용이 적고, 빠르게 종료될 수 있기에, 브루트포스 완전 탐색 알고리즘을 사용하기로 했다.

브루트포스 알고리즘이란?- 가능한 모든 경우의 수를 전부 탐색해서 정답을 찾는 알고리즘 기법이다. (무작정 시도한다고 해서 비효율적이라는 뜻은 아니다.)- 입력 크기가 작고 경우의 수가 제한적일 때 가장 단순하면서도 확실한 해결법.

코드 설계하기

문제의 Input을 받는다.
브루트포스 완전 탐색 알고리즘을 위해 이중 반복문을 사용한다.
- i, j번째의 값을 제외한 배열을 추출한다.
- 해당 배열의 총합을 계산한다.
- 총합이 100인지 확인하고, 맞으면 해당 배열을 출력하고 프로그램을 종료한다.

정답 코드

JavaScript

// 사용 언어 : Javascript

const fs = require('fs');

// 입력을 한 줄씩 받아서 문자열 배열로 만들고, 각 줄을 숫자로 변환
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const numbers = input.map(Number); // 숫자 9개가 들어옴

// 9명 중 2명을 제외하기 위한 이중 루프 (i < j 조합)
for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {

        // i, j 번째 난쟁이를 제외한 나머지 7명을 추출
        const newArr = numbers.filter((_, idx) => idx !== i && idx !== j);

        // 7명 키의 총합 계산
        let total = 0;
        for (const number of newArr) {
            total += number;
        }

        // 합이 정확히 100이면 정답이므로 출력 후 프로그램 종료
        if (total === 100) {
            newArr.sort((a, b) => a - b);  // 키를 오름차순 정렬
            newArr.forEach((num) => console.log(num)); // 한 줄씩 출력
            process.exit(); // 정답 찾았으므로 프로그램 종료
        }
    }
}

마무리하며

오랜만에 머리를 써서 문제를 분석하고 알고리즘과 로직을 고민하는 부분이 생각보다 어려웠지만, 생각만 해오던 코딩테스트를 실천할 수 있어서 의미 있는 순간이었다. 또한, chatGPT의 도움을 받지 않고, 최대한 순정 느낌을 살려서 생각 후 코딩을 진행할 수 있었던 점도 인상 깊었다. 전공 수업 중 알고리즘분석 수업에서 브루트포스 정렬 탐색 알고리즘을 배웠지만, 제대로 떠오르지 않았었는데, 검색하면서 알고리즘도 조금씩 공부하며 기억을 상기시킬 수 있어서 유익했다. 내일도 잘 풀어봐야지~

최근 글