14729번 칠무해

이분탐색을 이용한 하위 리스트 관리하기

이번 글에서는 Python의 bisect 모듈을 사용하여 하위 리스트를 관리하는 방법을 소개한다. 주어진 문제는 새로운 점수가 추가될 때마다 하위 7개의 점수만 유지하는 것이다. 이 과정에서 삽입 정렬을 사용하여 효율적으로 처리하는 방법을 살펴보겠다.

1. 입력 받기

먼저, 총 입력받을 점수의 개수를 입력받고, 초기 7개의 점수를 입력받는다.

n = int(input())
arr = sorted([float(input()) for _ in range(7)])

여기서 n은 총 점수의 개수다. 다음으로 sorted 함수를 사용하여 첫 7개의 점수를 오름차순으로 정렬한 리스트 arr을 생성한다.

2. 새로운 점수 추가하기

이제 남은 n-7개의 점수를 입력받고, 하위 7개의 점수를 유지하는 과정을 살펴보겠다.

for _ in range(n - 7):
    new_score = float(input())
    if new_score > arr[0]:
        bisect.insort(arr, new_score)
        arr.pop(0)

for _ in range(n - 7): : 처음 7개의 점수를 제외한 나머지 점수를 순차적으로 입력받기 위해 반복문을 사용한다.
new_score = float(input()) : 새로운 점수를 입력받는다.
if new_score > arr[0]: : 새로운 점수가 현재 하위 7번째 점수보다 클 경우에만 리스트에 추가한다. 이렇게 하면 불필요한 삽입을 방지할 수 있다.
bisect.insort(arr, new_score) : bisect.insort 함수를 사용하여 새로운 점수를 정렬된 리스트 arr에 적절한 위치에 삽입한다.
arr.pop(0) : 리스트의 첫 번째 원소, 즉 가장 작은 점수를 제거한다. 이로써 리스트 arr는 항상 하위 7개의 점수만을 유지하게 된다.

3. 결과 출력하기

최종적으로 하위 7개의 점수를 소수점 셋째 자리까지 출력한다.

open(1,'w').write('\n'.join(map(lambda x: "{:.3f}".format(x), arr)))

map(lambda x: "{:.3f}".format(x), arr) : 리스트 arr의 모든 원소를 소수점 셋째 자리까지 포맷팅한다.
'\n'.join(...) : 포맷팅된 문자열을 줄바꿈 문자로 연결하여 하나의 문자열로 만든다.
open(1,'w').write(...) : 표준 출력을 사용하여 결과를 출력한다.

최종 코드

위의 설명을 바탕으로 최종 코드를 다시 한 번 정리해보면 다음과 같다.

import bisect

n = int(input())
arr = sorted([float(input()) for _ in range(7)])
for _ in range(n - 7):
    new_score = float(input())
    if new_score > arr[0]:
        bisect.insort(arr, new_score)
        arr.pop(0)
open(1,'w').write('\n'.join(map(lambda x: "{:.3f}".format(x), arr)))

이 코드의 핵심은 bisect 모듈을 활용하여 삽입 정렬을 효율적으로 수행함으로써 항상 하위 7개의 점수만 유지하는 것이다. 이를 통해 새로운 점수가 추가될 때마다 매번 리스트를 재정렬하지 않고도 정렬된 리스트를 유지할 수 있다.

저작자표시 비영리 변경금지

붉은 각설탕