[백준 BOJ] 2309: 일곱 난쟁이 - python

오늘 풀어볼 문제는 일곱 난쟁이이다.

문제

일곱 난쟁이이를 찾아 오름차순으로 출력

풀이 과정

이 문제를 보고 먼저 떠올랐던 생각은 가능한 모든 조합을 구한 다음에 그 중 합이 100이 되는 걸 찾아서 출력하면 되겠다 였다.
좀 더 효율적으로 짤 수 있는 방법을 생각해 봤는데, 조합을 미리 구해놓는 게 아니라 for문으로 조합을 하나씩 구하면서 합이 100이 되면 break하는 방법이 떠올랐다.
근데 9명중에서 7명을 뽑는다는 걸 7중 for문으로 구현하려니까 끔찍해서 우선은 처음 생각한 대로 코드를 작성해 보았다.

from itertools import combinations

heights = [int(input()) for _ in range(9)]

height_combs = combinations(sorted(heights), 7)

for height_comb in height_combs:
    height_sum = sum(height_comb)
    if height_sum == 100:
        for height in height_comb:
            print(height)
        break

결과는 통과

좀 더 효율적인 코드는 뭘까 하고 다른 사람들의 풀이를 보았다.

다른 사람의 풀이

1. 난쟁이의 키 9개를 입력받아서 전부 더한다.
2. 이중 for문을 돌려서, total - 난쟁이 2명의 합 이 100인경우 9개의 배열에서 제거해준다.
3. 제거한 배열을 오름차순 정렬하여 순서대로 출력한다.

import sys

read = lambda: sys.stdin.readline().rstrip()

dwarf = [int(read()) for _ in range(9)]

total = sum(dwarf)
one = 0
two = 0

for i in range(9):
    for j in range(i+1, 9):
        if total - (dwarf[i] + dwarf[j]) == 100:
            one, two = dwarf[i], dwarf[j]
            break

dwarf.remove(one)
dwarf.remove(two)
dwarf.sort()

for i in dwarf:
    print(i)

위의 코드의 로직대로 푼 사람들이 많았다.
확실히 모든 조합을 구하지 않고, 중간에 멈추니까 더 빠를 것이라고 생각된다.
근데 아무래도 나올 수 있는 조합의 개수가 매우 적기 때문에 이 문제에서는 유의미한 시간 차이를 주진 않는 것 같다.