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

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

난이도: 브론즈1

▶ 문제 탐색하기

◇ 원하는 출력 조건:

1.  7명 키의 합이 100
2.  이 때 키를 오름차순으로 정렬

Input의 크기가 매우 작으므로 모든 경우의 수를 탐색해야한다.  완전 탐색(Input의 크기가 작을 때 사용)

아이디어: 9명의 난쟁이 중 제외할 2명의 난쟁이를 우선 선택한다. -> 코테에서는 1억 번의 연산이 대략 1초 정도 걸리므로 널널하다.

□ 아이디어

 Way1: 키의 합을 확인 후에 제외하여 7명을 배열에 넣고 다시 정렬

 Way2: 9명의 Input을 받고 먼저 정렬 후에 제외

 

☆ Python은 sort() 함수가 존재하는데 평균적으로 N개의 원소를 정렬할 때, O(NlogN)의 시간복잡도를 갖는다. 

 

▶ 코드 설계하기

1. 문제의 Input을 받는다.
2. Input을 받으며 9명 키의 합을 구한다.
3. 9명 키의 배열을 미리 정렬한다.
4. 9명 중 2명을 제외하는 모든 경우의 수를 탐색하는 for loop를 구현한다.
5. 제외된 2명을 빼고 총 합이 100을 만족하는지 확인한다.
6. 총 합이 100을 만족할 경우 정답을 출력하고 for loop를 탈출한다.

▶ 시도 회차 수정 사항

• 배열에서 2명을 제외하는 법으로는 remove(), pop() 등을 사용하려 했으나 원소 하나씩 제거되는 메서드 이므로 인덱스 변경에 신경써줘야했다. → 그래서 큰 인덱스의 원소를 지우고, 나머지를 지우는 방식으로 했음.
• 다른 방안: 'continue' 문을 사용한다. 현재 반복을 건너 뛰고 반복문의 다음 반복으로 넘어가게한다. 

# 제외된 2명의 난쟁이를 빼고 배열을 출력하는 함수
def print_ans(arr, a, b):
    for i in range(9):
        if i == a or i == b:
            continue
        print(arr[i])

▶ 정답

# 2309번: 일곱난쟁이
def find_dif(arr, dif): # 두 개의 숫자 중 합이 dif에 해당하는 숫자를 찾는다.
  # 배열에서 두 개의 숫자의 합이 dif가 되는 것을 찾는건데 sort라고 봐도 될듯.
  found = False
  for i in range(len(arr)):
    for j in range(i+1, len(arr)):
      if arr[i] + arr[j] == dif:
        second = arr.pop(j) # 먼저 큰 인덱스의 원소를 제거
        first = arr.pop(i)
        found = True
        break
    if found:
      break
  if found:
    #print(f"{first}, {second}")
    arr.sort()
    for element in arr:
      print(element)
  else:
    print("none")
        #  arr.remove(arr[i]) Index error가 뜬다. 
        # arr.remove()는 한 번에 하나의 원소만 제거 가능하다.
        # 근데 원소를 제거하는 동안 인덱스가 변경될 수 있

def solution():
  hap = 0 # 로컬변수 초기화/ Unbound local error
  arr = [] # 배열이 루프 밖에 있어야 초기화가 안된다.
  for i in range(9):
    height = int(input())
    arr.append(height)
    hap += height # 로컬변수가 선언되기 전에 사용되었기 때문에 0으로 초기화해줘야한다.
  dif = hap - 100
 # print(arr) # arr = [20, 7, 23, 19, 10, 15,1 25, 8, 13]
 # print(dif) # dif = 40
  find_dif(arr, dif)

solution()

▶ 추가 풀이

import sys
# 제외된 2명의 난쟁이를 빼고 배열을 출력하는 함수
def print_ans(arr, a, b):
    for i in range(9):
        if i == a or i == b:
            continue
        print(arr[i])
        
arr = []
total = 0
for i in range(9):
    arr.append(int(sys.stdin.readline())) 
    total += arr[i]
arr.sort()

found_ans = False
for i in range(0, 9):
    # 정답을 만족했을 경우 for문을 탈출합니다.
    if found_ans:
        break
    for j in range(i + 1, 9):
        now = total - arr[i] - arr[j]
        if now == 100:
            print_ans(arr, i, j)
            found_ans = True
            break

 

arr.append(int(sys.stdin.readline())) 

코테에서 input()의 입력보다 sys.stdin.readline()이 쓰이는 이유??