[백준] 2309 일곱난쟁이 Python

 

1. 문제

돌아온 아홉 명의 난쟁이 중에서, 키의 합이 100인 일곱 난쟁이를 구하여 오름차순으로 출력하는 프로그램

https://www.acmicpc.net/problem/2309

 

2. 알고리즘 분류

* 브루트포스 알고리즘

* 정렬

 

3. 접근 방식

itertools 의 combination 을 알게 되어 조합을 이용하였다 

Permutation 과 Combination 개념 정리 

[TIL] itertools 순열 조합 구하기 Python

 

4. 전체 코드

# 일곱 난쟁이 키의 합이 100 일 때, 돌아온 9명 중에
# 일곱 난쟁이를 찾아서 오름차순으로 출력하는 프로그램

import itertools

# 돌아온 난쟁이 N 으로 설정하기 
N = 9

# N 만큼의 숫자를 엔터로 입력 받기 
height_list = []
for i in range(N):
    height_list.append(int(input().strip()))

# 9개 중 7개를 고르는 조합을 생성 
combinations = itertools.combinations(height_list, 7)

# 조합 comb 의 합이 100일 때 result 에 값 저장하고
# result 리스트의 값을 바로 순회하여 height 출력 
for comb in combinations:
    if sum(comb) == 100:
        result = sorted(comb)
        for height in result:
            print(height)
        break

 

5. 추가 - sorted() 와 sort() 

itertools.combination() 에서 생성된 조합은 튜플이기 때문에

sorted() 대신 sort() 를 쓰고 싶다면 아래와 같이 for 문을 작성하면 된다

sorted() 와 sort() 개념 정리

for comb in combinations:
    if sum(comb) == 100:
        comb = list(comb)  # tuple -> list 변환
        comb.sort()  # 리스트 자체를 오름차순으로 정렬
        for height in comb:
            print(height)
        break

 

6. 추가 - Python Comprehension

Python Comprehension 반복문을 간결하게 한 줄로 표현하여 리스트, 딕셔너리, 집합 등을 생성할 수 있는 강력한 문법 

List Comprehension 리스트 컴프리헨션 - 반복문을 한 줄로 간단하게 표현하는 파이썬의 강력한 기능 중 하나 

for i in range(N):
    height_list.append(int(input().strip()))
# 이 두 문장을 아래 한 문장으로 표현할 수 있다 feat 파이썬 컴프리헨션

height_list = [int(input().strip()) for _ in range(N)]

 

+ 아래는 파이썬 컴프리헨션 아님

combinations = itertools.combinations(height_list, 7)
for comb in combinations:
        
# 이 반복문도 아래와 같이 표현 가능하다 
# 이건 컴프리헨션 아니고 일반적인 for문

for comb in itertools.combinations(height_list, 7):