파이썬(Python) 정렬된 리스트에 요소 삽입하기: 브루트 포스와 bisect 모듈 활용법

이 글에서는 정렬된 순서를 유지하면서 리스트에 새로운 요소를 삽입하는 방법을 알아봅니다.

문제 정의 – 정렬된 상태의 리스트가 주어졌을 때, 기존의 정렬 순서를 깨지 않으면서 새로운 요소를 올바른 위치에 삽입해야 합니다.

이 문제는 크게 두 가지 방법으로 해결할 수 있습니다.

방법 1: 브루트 포스(완전 탐색) 방식

리스트를 처음부터 끝까지 순회하면서 새 요소보다 큰 값을 가진 첫 번째 위치를 찾고, 그 위치에 요소를 삽입하는 방법입니다.

예제 코드

def insert(list_, n):
    # 삽입할 위치 탐색
    for i in range(len(list_)):
        if list_[i] > n:
            index = i
            break
    else:
        index = len(list_)  # 모든 요소보다 클 경우 맨 뒤에 삽입
    # 요소 삽입
    list_ = list_[:index] + [n] + list_[index:]
    return list_

# 실행 예시
list_ = [1, 2, 4, 5]
n = 3
print(insert(list_, n))

출력 결과

[1, 2, 3, 4, 5]

숫자 3은 2보다 크고 4보다 작기 때문에 인덱스 2의 위치에 삽입되며, 전체 리스트의 정렬 상태는 그대로 유지됩니다.

방법 2: bisect 모듈 활용

파이썬 표준 라이브러리인 bisect 모듈을 사용하면 이진 탐색(binary search)을 통해 삽입 위치를 효율적으로 찾을 수 있습니다. 특히 bisect.insort() 함수는 위치 탐색과 삽입 과정을 한 번에 처리해 주기 때문에 코드가 매우 간결해집니다.

예제 코드

# 내장 bisect 모듈 사용
import bisect

def insert(list_, n):
    bisect.insort(list_, n)
    return list_

list_ = [1, 2, 4, 5]
n = 3
print(insert(list_, n))

출력 결과

[1, 2, 3, 4, 5]

두 방법의 차이점: 브루트 포스 방식은 리스트를 처음부터 순회하기 때문에 최악의 경우 O(n)의 시간이 걸리는 반면, bisect 모듈은 이진 탐색을 활용해 O(log n) 시간 안에 삽입 위치를 찾습니다. 따라서 데이터 양이 많은 경우 bisect 모듈을 사용하는 것이 훨씬 효율적입니다.

위 예제에서 사용된 모든 변수는 지역 범위(local scope) 내에서 선언되며, 함수 호출이 종료되면 함께 소멸합니다.

결론

이 글에서는 정렬된 리스트에 요소를 삽입하는 두 가지 방법, 즉 직접 구현하는 브루트 포스 방식과 파이썬 내장 bisect 모듈을 활용하는 방법을 살펴보았습니다. 학습 목적이라면 직접 구현해 보는 것도 좋지만, 실무에서는 성능과 코드 간결성 면에서 bisect 모듈을 사용하는 것을 권장합니다.