[백준 2309] 일곱 난쟁이

문제

9명의 난쟁이가 있다. 백설공주는 일곱 난쟁이 키의 합이 100이라는 것을 통해 9명 중 진짜 일곱 난쟁이를 판단하려고 한다.

 

입력

9개의 정수를 입력한다.

 

출력

조건에 맞는 7개의 키를 오름차순으로 출력한다.

---

처음 이 문제를 보고 바로 7개의 경우의 수를 구하여 합을 비교하는 식으로 구성을 했다. 하지만 입력받은 9개의 키를 모두 더하고 2개만 빼서 100이 되는지 확인하면 되는 것을 알았다. 

 

1. 입력받은 키를 정렬한 뒤에 모두 합한다.

2. 이중 for문을 통해 2개의 키를 선택해 키의 합에서 뺀다.

3. 2번의 결과가 100이라면 두 개의 키를 리스트에서 제거한다.

==> 이때 if문 안에 바로 인덱스를 활용해 remove()를 실행했다. 하지만 첫 번째 remove()가 실행되면 인덱스가 모두 변경되어 error가 발생했다. 따라서 인덱스가 아닌 인덱스에 해당되는 원소를 따로 저장하여 remove()하는 것으로 변경하였다.

4. 최종적으로 일곱 난쟁이의 키를 출력한다.

 

height = []
for _ in range(9):
    height.append(int(input()))

total=sum(height)
height.sort()

a=0
b=0
for y in range(len(height)-1):
    for x in range(y+1,len(height)):
        if total - (height[y] + height[x]) == 100:
            a=height[y]
            b=height[x]
            height.remove(a)
            height.remove(b)
            break

for h in height:
    print(h)

---

문제에서 주어진 조건을 다르게 활용할 수 없을까라는 질문을 통해 좀 더 짧고 빠른 알고리즘을 구성하도록 해야한다.