2309) 일곱난쟁이

📌 문제 탐색하기

• 9명의 난쟁이 중 키의 합이 100이 되는 7명의 난쟁이를 구하는 문제
• 0 < 키 <= 100 자연수
• 출력은 키 합이 100인 난쟁이 7명 조합 아무거나 단, 오름차순 정렬

가능한 시간복잡도

(이 부분은 조금 더 공부하겠습니다😭)

알고리즘 선택

📍 해설지 참고

• 브루트포스 알고리즘(완전탐색/전체탐색)
• 정렬

📌 코드 설계하기

1. 문제의 input 받아 변수에 저장 (list 사용)
2. 9명의 난쟁이 중 7명의 난쟁이 선택 후 합이 100인지 확인
3. 합이 100이면 list 오름차순 정렬
4. 출력

📍 해설지 참고 후
2번 수정 -> 9명의 난쟁이 중 제외할 2명 구해서 9명 키 합 - 제외할 2명 키 == 100인지 확인

📌 시도 회차 수정 사항 (Optional)

1회차

## 리스트
heights = []
for i in range(9):
    heights.append(int(input()))

total_sum = 0
for i in range(10):
   result = heights[i : i + 7]
   total_sum = sum(result)

   print(f"i : {i} \n result : {result} \n sum : {total_sum}\n")

   if total_sum == 100:
     result.sort()
     print(result)

• 리스트에서 7명을 뽑아내 합을 구한 후 100이 넘는지 체크하는 로직으로 구성했다
• print 해보니 i가 커질수록 끝값이 인덱스에서 벗어나서 리스트에 7개 미만으로 들어왔다..

2회차

import itertools

## 리스트
heights = []
for i in range(9):
    heights.append(int(input()))

total_sum = 0
result = list(itertools.combinations(heights, 7))

for r in result:
    total_sum = sum(r)

    if total_sum == 100:
        sorted_r = sorted(r)
        print(sorted_r)
        break
    

• heights 리스트에서 7개의 모든 조합을 찾기 위해 구글링..

itertools.combinations(리스트, r):

• 이 함수는 주어진 리스트에서 r개의 요소를 뽑는 모든 조합을 반환
• combinations 객체는 반복자(iterator)이기 때문에, 리스트로 변환하거나 for문으로 순회하여 사용!!!
• import itertools 필요

r.sort()는 튜플에서는 사용할 수 없기 때문에 sorted()로 처리!!

3회차

📍 해설지 참고

• 9명의 난쟁이 중 7명을 선택(완전 탐색)하는 것이 아니라, 9명의 난쟁이 중 제외할 2명의 난쟁이를 선택
  - 생각의 전환 필요!!!
• 2명의 난쟁이를 따로 뽑을 필요없이, 이중 for문으로 제외한 두명의 키를 9명 전체 합에서 뺐을 때, 100을 만족하는지 확인

완전 탐색은 input의 크기가 유난히 작으면서 모든 경우의 수를 탐색하는 코드 구현이 가능할 경우에!
모든 경우의 수를 빠뜨리지 않고 탐색할 수 있게 구현하는 것이 중요

📌 정답 코드

import sys 
def print_result(arr, a, b):
    for i in range(9):
        if i == a or i == b:
            continue
        print(arr[i])

# 1. input 받기
heights = []
for i in range(9):
    heights.append(int(sys.stdin.readline())) # import sys 필요
    # heights.append(int(input()))

# 2. 아홉 난쟁이 키의 합 미리 구해두기
total_sum = sum(heights)
# 3. 미리 정렬
heights.sort()

# 4. 9명 중 2명을 제외하는 모든 경우의 수를 탐색하는 for loop 구현
found = False
for i in range(9):
    if found:
        break
    for j in range(i + 1, 9):
        # 5. 제외된 2명을 빼고 총 합이 100인지 확인
        now = total_sum - heights[i] - heights[j]

        # 6. 100이면 출력, for loop 탈출  
        if now == 100:
            print_result(heights, i, j)
            found = True
            break

sys.stdin.readline()을 왜 사용하나요?
→ 빠른 입출력을 위해 사용합니다. input()과 정확히 동일한 역할을 하지만 더 빠른 입출력을 지원!

📌 부족한 점

• 알고리즘 기법에 대한 이해가 없어서 설계가 너무 부족하다..
• 완전탐색(브루트 포스) 이론 공부하고 관련 문제 3개 더 풀자
• 문제를 보는 시선의 전환 또한 필요하다.. 이것도 많이 풀어보면 늘겠지...?