[Python] 리스트의 원소 추가 방법 및 관련 문제

개요

코테 문제를 풀다 시간 복잡도를 보기엔 초과할 것 같지 않았던 코드가 계속 시간이 초과한 문제가 발생했다.

알고보니, 리스트에 원소 추가한 방식이 문제였고 정리해두려 정리해둔다.

 

 

추가 방식

1. Append (뒤에 추가)

a = []
a.append("one")

평균 삽입 시간 복잡도는 O(1).

만약 원소 추가할때 리스트에 할당한 초기 메모리를 초과한다면 새로 할당 작업을 해야하니 O(n)이 할당된다.

 

2. Insert(삽입 위치 지정)

a = ["one","three"]
a.insert(1,"two")

삽입 시간 복잡도는 O(n).

내가 틀린 부분이다. 난 insert(0, value) 처럼 사용하면 큐와 비슷하게 O(1) 로 사용 가능할거라 착각했지만,

사실 당연하게도 첫 자리에 원소를 삽입 후 나머지 원소를 뒤로 이동하는 과정에서 O(n)의 시간 복잡도가 소요된다.

 

3. 슬라이싱 및 여러 원소 동시 삽입

a = ["one","two"]
a = [*a, "three"]

a = a[0:2] + ["2.5"] + a[2:]

삽입 시간 복잡도는 O(n).

 

4.Expend

a = ["one","two"]
a.extend([3,4,5,6,7])

삽입 시간 복잡도는 O(k) 

k는 삽입 원소수. 내부적으로 O(1)의 Append를 여러번 한다고 보면 이해가 쉽다

(* 단 메모리 할당 차원에서 한개씩 원소를 Append 하는 것 보다 한번에 할당하니 좀더 성능이 좋다 )

 

-> 참고로 파이썬은 리스트를 선언할때 약간의 여유 공간을 확보해둔다. 그리고 첫 원소를 삽입하면 4개 정도 분량의 공간을 미리 확보하고, 그 후 크기 증가에따라 e 증가 방식으로 증가한다. (대략 1,125 ~ 2배)

 

 

참고 문제

스택만 활용하면 풀 수 있는 문제니 참고해도 좋을 것 같다.

https://school.programmers.co.kr/learn/courses/30/lessons/154539#

프로그래머스

 

 

마무리

다음엔 헷갈리지 말자!