일곱 난쟁이 풀이: 두 명을 제외하는 완전탐색

일곱 명을 직접 고르면 아홉 명 중 일곱 명의 모든 조합을 생각해야 합니다. 반대로 정답에서 빠질 두 명을 고르면 확인해야 할 대상이 단순해집니다. 전체 키의 합을 구한 뒤 두 키를 빼서 100이 되는지만 검사하면 됩니다.

두 후보는 서로 다른 인덱스로 선택해야 하므로 바깥 반복문의 다음 위치부터 안쪽 반복문을 시작합니다. 이 방식은 같은 사람을 두 번 고르지 않으며, 순서만 바뀐 동일한 쌍도 다시 검사하지 않습니다.

조건을 만족한 두 원소를 배열에서 제거할 때는 큰 인덱스를 먼저 삭제해야 합니다. 앞쪽 원소부터 지우면 뒤쪽 원소의 위치가 하나 당겨져 원하지 않는 값이 삭제될 수 있기 때문입니다.

전체 합을 T라고 하면 제외할 두 키의 합은 T - 100이어야 합니다. 이 등식으로 목표를 바꾸면, 일곱 원소의 조합을 직접 구성하지 않고 두 원소의 쌍만 확인할 수 있습니다. 아홉 명 중 두 명을 고르는 쌍은 최대 36개뿐이므로 별도의 최적화 자료구조가 필요하지 않습니다.

입력 순서를 유지해야 하므로 정렬은 사용하지 않습니다. 정렬한 뒤 일곱 값을 출력하면 합은 맞더라도 원문이 요구한 순서가 달라질 수 있습니다. 처음 배열의 순서를 보존한 복사본에서 두 원소만 제거하면 나머지 원소의 상대적 순서가 그대로 남습니다.

키는 모두 서로 다르지만, 탐색은 값이 아니라 인덱스를 기준으로 진행합니다. first와 second가 서로 다른 위치를 가리키고, 안쪽 반복이 항상 first + 1에서 시작하므로 자기 자신을 선택하거나 같은 쌍을 반대 순서로 다시 확인하지 않습니다.

알고리즘 설계

1. 아홉 키의 전체 합을 계산합니다.
2. 이중 반복문으로 제외할 두 인덱스 i와 j를 선택합니다.
3. 전체 합 - heights[i] - heights[j]가 100인지 확인합니다.
4. 조건이 맞으면 뒤쪽 인덱스 j, 앞쪽 인덱스 i 순서로 제거하고 탐색을 끝냅니다.
5. 남은 일곱 값을 원래 입력 순서대로 출력합니다.

정답 일곱 명의 합이 100이라면 제외되는 두 명의 합은 반드시 전체 합에서 100을 뺀 값과 같습니다. 따라서 가능한 두 인덱스 쌍을 빠짐없이 확인하면 정답 후보를 찾을 수 있습니다. 입력 크기는 아홉 개로 고정되어 있어 모든 쌍을 확인해도 충분히 빠릅니다.

정확성은 완전성과 보존성으로 나누어 확인할 수 있습니다. 완전성 측면에서 이중 반복문은 first < second인 모든 두 인덱스 조합을 한 번씩 검사합니다. 문제 조건상 답이 존재한다면 제외해야 할 두 인덱스도 이 목록에 반드시 포함됩니다.

보존성 측면에서는 조건을 만족하기 전까지 배열을 수정하지 않습니다. 정답 쌍을 찾은 뒤에만 두 원소를 제거하며, 큰 인덱스를 먼저 지워 작은 인덱스의 위치가 달라지지 않게 합니다. 제거되지 않은 일곱 원소는 처음 배열에서의 상대적 순서를 그대로 유지합니다.

가능한 답이 여러 개라면 가장 먼저 발견한 쌍에서 탐색을 끝냅니다. 원문은 가능한 답 중 하나를 허용하므로 모든 정답 쌍을 수집할 필요가 없습니다. 이 조기 종료는 출력의 유효성을 바꾸지 않으면서 불필요한 반복만 줄입니다.

제공된 코드의 핵심 접근은 정확합니다. 다만 answer = arr는 같은 배열을 가리켜 원본까지 변경하고, ==는 형 변환을 허용합니다. 아래 정답 코드는 배열을 복사해 입력값을 보존하고, 엄격한 비교 연산자 ===를 사용합니다. 또한 상태 변수 대신 레이블이 있는 break로 두 반복문을 한 번에 종료합니다.

아래 완성 코드를 Node.js용 solution.cjs로 저장합니다. input.txt에는 예제 키 20, 7, 23, 19, 10, 15, 25, 8, 13을 한 줄에 하나씩 적습니다. 사람 수 9를 첫 줄에 추가하지 않습니다. Bash·명령 프롬프트에서는 node solution.cjs < input.txt, PowerShell에서는 cmd /c “node solution.cjs < input.txt”로 실행합니다. 기대 출력은 20, 7, 23, 19, 10, 8, 13의 일곱 줄입니다. 출력 개수·합 100·입력 상대 순서를 함께 확인하세요.

const fs = require('fs');

const heights = fs
    .readFileSync(0, 'utf8')
    .trim()
    .split(/\s+/)
    .map(Number);

function findSevenDwarfs(inputHeights) {
    const result = [...inputHeights];
    const totalHeight = result.reduce(
        (sum, height) => sum + height,
        0
    );

    search:
    for (let first = 0; first < result.length - 1; first++) {
        for (let second = first + 1; second < result.length; second++) {
            if (totalHeight - result[first] - result[second] === 100) {
                result.splice(second, 1);
                result.splice(first, 1);
                break search;
            }
        }
    }

    return result;
}

console.log(findSevenDwarfs(heights).join('\n'));

split(/\s+/)는 줄바꿈과 공백을 모두 구분자로 처리하므로 아홉 줄 입력을 숫자 배열로 바꿉니다. result는 입력 배열의 복사본이어서 삭제 이후에도 원본 inputHeights는 유지됩니다. 삭제 전에는 항상 second가 first보다 크므로 뒤쪽 원소를 먼저 지우는 순서도 보장됩니다.

정답 쌍을 찾은 뒤에는 더 탐색할 필요가 없습니다. 레이블 search에 대한 break가 두 반복문을 모두 끝내고, 일곱 개만 남은 배열을 그대로 반환합니다. 정렬을 하지 않으므로 결과의 상대적인 순서는 입력과 같습니다.

복잡도와 검증

전체 합 계산은 O(n), 두 후보를 찾는 이중 반복문은 O(n²)입니다. 따라서 전체 시간 복잡도는 O(n²)입니다. 정답 코드가 입력 배열을 복사하므로 추가 공간 복잡도는 O(n)입니다. 이 문제에서는 n = 9로 고정되어 제한 안에서 여유롭게 실행됩니다.

제공 학습 자료 예제의 전체 합은 140이며, 15와 25를 제외하면 남은 합이 100입니다. 코드는 두 값을 뒤쪽 인덱스부터 제거하므로 20, 7, 23, 19, 10, 8, 13의 입력 순서를 유지합니다. 모든 키가 서로 다르다는 조건 덕분에 값이 아니라 인덱스로 두 후보를 관리해도 혼동이 없습니다.

출력 전에는 일곱 값의 합과 개수, 입력에서의 상대 순서를 함께 확인합니다. 이 세 조건은 정답 후보를 찾는 일과 출력 형식을 맞추는 일을 구분하는 기준입니다.

최댓값이 100인 입력도 별도 처리가 필요하지 않습니다. 아홉 키의 전체 합은 최대 900이므로 모든 계산은 JavaScript의 안전한 정수 범위보다 매우 작습니다. 덧셈과 뺄셈만 사용하므로 부동소수점 오차를 고려할 상황도 없습니다.

서로 다른 키라는 조건은 같은 숫자를 구분하는 추가 장치를 만들지 않아도 된다는 뜻입니다. 그러나 정답 코드는 값 검색이 아니라 인덱스 쌍을 사용하므로, 탐색 과정 자체는 각 위치를 명확하게 구분합니다. 삭제할 위치가 결정된 뒤에만 배열을 바꾸기 때문에 아직 검사하지 않은 후보가 중간에 이동하는 문제도 생기지 않습니다.

배열을 수정하지 않고 filter로 두 인덱스를 제외한 새 배열을 만드는 방법도 가능합니다. 이번 코드는 제공된 시도의 splice 접근을 살리면서 원본 훼손만 막기 위해 먼저 복사본을 만들었습니다. 원래 시도의 핵심을 유지하고 부작용을 줄인 수정 결과라는 점이 구현 선택의 기준입니다.

경계 조건에서도 각 키는 100 이하의 자연수이므로 JavaScript의 일반 정수 연산 범위에 충분히 들어갑니다. 가능한 답이 여러 개인 경우에는 첫 번째로 찾은 쌍을 사용하며, 문제 조건에서 허용하는 출력 방식과 일치합니다.

마지막으로 출력 단계는 계산 과정의 중간값이나 제외된 두 키를 표시하지 않습니다. 정답 배열의 일곱 값만 줄 단위로 연결하므로 문제에서 요구한 출력 형식에 정확히 대응합니다. 탐색, 삭제, 출력의 역할이 분리되어 있어 각 단계도 독립적으로 확인할 수 있습니다.