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

Key Point

👉 intertools 모듈 사용하기

 

정리

👉 combinations 과 permutations 와 차이점은?

 

- permutations 은 중복이 되어도 순서가 다른 케이스이면 모두 포함
   >>  (1,2,3) (1,3,2) 존재, 다른 의미임.

- combinations 은 중복 없음

  >> (1,2,3)외의 같은 요소 포함된 것 없음

 

 

처음 풀이 (정답 O)

from itertools import permutations

list_height = []

for i in range(9):
    list_height.append(int(input()))

list_height.sort()

# sum(list) = > 1차원 리스트의 합임.
for i in permutations(list_height, 7):  
    if(sum(i) == 100):
        print(i[0])
        print(i[1])
        print(i[2])
        print(i[3])
        print(i[4])
        print(i[5])
        print(i[6])
        break

 

 

더 나은 풀이

from itertools import combinations

h = [int(input()) for _ in range(9)]
for i in combinations(h,7):
    if (sum(i) == 100):
        for j in sorted(i):
            print(j)

 

 

 

그 외의 풀이

이중 for 문 / 9명중 7명을 뽑는 건, 9명 중 2명을 뽑는다는 것과 같은 의미이다. 그렇다면, 이중 for문을 통해 2명을 뽑고 그 외의 난쟁이 키 합을 구하면 된다. 

N이 9이기 때문에, 할만 하다.

 

 

그 외의 내 질문 및 멘토 답변 사항

 

질문. 파이썬 내부적으로 리스트 내에서 in 같은 거나, sort 같은 메서드 사용을 하는건
시간복잡도에 고려를 하지 않아도 되는 이유가 뭔가요?
이미 성능적으로 아주 빨라서 그런가요?
답변. 고려를 안해도 되는 것은 아닙니다. 고려해야 합니다. 파이썬 리스트 슬라이싱은 그냥 for문 쓴 것과 똑같은 방식이라 O(N) 으로 알고 있습니다. 언어들이 기본으로 제공하는 정렬은 다 O(NlogN) 입니다.

질문. 혹시 백준 풀때, 다른 ide에서 충분히 풀어 본후 완성된 거 같은 답안을 제출하는게 아니라, 바로바로 백준에서 푸는게 좋나요?
답변. 그냥 IDE에서 푸는게 일반적입니다. 백준에서 바로 푸는 사람은... 없지 않을까요?