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

 

📚 일곱 난쟁이

 

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

20
7
23
19
10
15
25
8
13

예제 출력 1 복사

7
8
10
13
19
20
23

 

 

 

✍ 접근

• 브루트포스 알고리즘 방식으로 접근했다.
  1. 난쟁이가 9명밖에 주어지지 않았고
  2. 아무리 많은 for 문을 돈다고 하더라도 시간복잡도에 무리가 없을 것 같았다.

 

 

 

정답 코드 1 ( 첫 풀이 ) _ 다른 코드 참고

import sys

input = sys.stdin.readline
arr=[]

for _ in range(9):
    arr.append(int(input()))
sums = sum(arr)
one = 0
two = 0  
for j in range(8):
    for k in range(j+1,9):
        if sums-(arr[k]+arr[j]) == 100:
            one,two = arr[j], arr[k]
            break

arr.remove(one)
arr.remove(two)
arr.sort()
for x in arr:
    print(x)

• arr에 모든 난쟁이를 넣어둔다
• 난쟁이 키의 총합을 sums로 만들어둔다
• for문을 난쟁이가 중복되지 않게 두 번 돌면서
  1. 난쟁이 두 명을 뺐을 때 100이 되는 경우
  2. 난쟁이 one, two에 각각 값을 넣어준다
• arr에서 one과 two를 remove를 사용해서 제거한 뒤
• 배열(arr)을 정렬한 후
• for문을 돌면서 난쟁이 키를 오름차순으로 하나하나 찍어준다

 

✨ 특징

• 백설공주의 난쟁이가 아닌 난쟁이들의 키를 one과 two에 따로 입력해준다.
• 처음 구해진 한 번의 값이 도출되면 for문으로 하나의 중첩 for문만 빠져나간다

 

 

정답 코드 2 ( 내 풀이 )

arr = []
for i in range(9):
    arr.append(int(input()))
sums = sum(arr)

def F():
    for i in range(8):
        for j in range(i+1,9):
            if sums - (arr[i]+arr[j]) == 100:
                return [arr[i],arr[j]]


res = set(arr)-set(F())
res = sorted(list(res))
for x in res:
    print(x)

• arr에 모든 난쟁이를 넣어둔다
• 난쟁이 키의 총합을 sums로 만들어둔다
• 함수 F 안에서 for문을 난쟁이가 중복되지 않게 두 번 돌면서
  1. 난쟁이 두 명을 뺐을 때 100이 되는 경우
  2. 난쟁이 두 명의 키를 배열로 return해주며 함수를 중료한다
• 난쟁이들의 키가 겹치지 않는다는 점에서 착안해 arr에서 함수의 return 값을 제거해준다
• 남은 난쟁이들의 값을 다시 list로 만들어 정렬해준다
• for문을 돌면서 정렬한 난쟁이들의 키를 찍어준다.

 

 

 

헷갈릴 수 있는 부분

print(arr)
for i in range(8):
    for j in range(i+1,9):
        if sums - (arr[i]+arr[j]) == 100:
            arr.remove(arr[i])
            arr.remove(arr[j])

만약 이렇게 arr.remove를 연속해서 써주면 문제가 생긴다

왜냐하면 arr[j]가 8이었을 경우

위에서 arr[i]를 삭제했기 때문에 list의 길이를 벗어나버리기 때문.

간과할 수 있는 부분이니까 확실히 기억하자

 

 

 

⭐ 배움

• 브루트포스 알고리즘을 해야 할 때와 다른 알고리즘을 이용해야 할 때를 잘 구분해야 할 것 같다.