[백준] 2309: 일곱 난쟁이 (Python)

2309: 일곱 난쟁이

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.

풀이

 9명의 난쟁이 중 7명을 골라 합이 100인지 비교하는 것이니 연산 횟수는 9C2라고 생각했다. 하지만 후에 코드를 짜다보니 9*8로 풀게 되었다. 7명을 골라 일일이 더하기보다 전체 합에서 2명의 키를 빼는 것이 더 간편하기 때문에 그렇게 풀었다.

 코드를 짜면서 두 가지 문제를 겪었는데, 첫번째는 j의 range를 0~8에서 i를 제외한 범위로 설정하고 싶었는데 if문과 continue를 사용하는 방법이 생각이 안나서 두번의 for문을 썼다가 IndexError를 마주한 것이다. 앞선 for문에서 정답이 나올 경우 리스트의 원소 삭제가 이루어졌기 때문에 인덱스 에러가 발생한 것이다. 그래서 find 변수를 통해 답이 발견되면 밑의 for문은 검사하지 않도록 했다. 또한 밖의 for문에서도 find를 검사하여 true가 되면 반복문을 종료하도록 했다. 그러나 이후에 두번째 문제가 발생했는데, arr의 원소 삭제를 del arr[i], del arr[j]로 해서 i에서 원소를 삭제하면서 j의 인덱스가 변경돼 잘못된 결과가 출력된 것이다. 이를 해결하기 위해 a, b에 arr[i]와 arr[j]의 값을 저장해두고 a, b의 값을 가진 원소를 삭제하는 것으로 코드를 수정하였다. 이렇게 완성한 코드는 다음과 같다. 

# 2309: 500 - 브루트 포스 - 일곱 난쟁이
arr = []
result = 0
find = False
for i in range(9):
    arr.append(int(input()))
for i in range(9):
    result = sum(arr) - arr[i]
    for j in range(9):
        if i == j:
            continue
        result -= arr[j]
        if result == 100:
            a, b = arr[i], arr[j]
            arr.remove(a)
            arr.remove(b)
            find = True
            break
        else:
            result += arr[j]
    if find == True:
        break
    result = 0
arr.sort()
for i in range(7):
    print(arr[i])

 정답 판정을 받은 후 다른 사람들의 풀이를 보았는데 로직은 맞았으나 구현에 있어 내가 불필요한 부분을 많이 적었다는 것을 알게 되었다. https://kyoung-jnn.tistory.com/entry/백준2309번파이썬Python-일곱-난쟁이-Brute-force 이 블로그의 도움을 받아 코드를 간결하게 수정하고 어디를 왜, 어떻게 수정했는지 주석으로 달았다.

# 2309: 500 - 브루트 포스 - 일곱 난쟁이
arr = [int(input()) for i in range(9)] # 값을 입력 받는 코드를 간결하게 표현
total = sum(arr) # for문 밖에서 미리 총 합을 계산해두기 - 반복해서 계산할 필요 없음
for i in range(9):
    for j in range(i+1, 9): # 불필요한 중복 검사 제거 위해 i+1부터 검사
        if (total - arr[i] - arr[j]) == 100: # result 변수 선언 없이 바로 비교
            a, b = arr[i], arr[j]
            arr.remove(a)
            arr.remove(b)
            arr.sort()
            for i in range(len(list)):
               print(list[i]) # 답을 찾고 바로 출력
            break
    if len(list)<9: # 정답을 찾아서 배열의 길이가 7이 되면(==9보다 작아지면)
        break # 바깥 for문도 종료