[WEEK02] 12일차. 리스트 슬라이스, deque, 이분 탐색

리스트 슬라이스 사용하기

a[::] 리스트 전체 가져오기. a[:]와 결과가 같음.

a[7::2] 인덱스 7부터 2씩 증가시키면서 리스트 마지막 요소까지 가져오기

a[5:1:-1] 인덱스 5부터 2까지 1씩 감소시키면서 요소 가져오기

a[::-1] 인덱스 1씩 감소시키면서 요소 가져오므로 리스트 반대로 뒤집음.

a[-1::-1] 마지막 인덱스부터 -1씩 빼면서 처음까지 가져오기. a[::-1]과 같다.

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

print(a[:])
print(a[::])
print(a[7::2])
print(a[5:1:-1])
print(a[::-1])
print(a[-1::-1])

>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> [8, 10, 12, 14, 16]
>>> [6, 5, 4, 3]
>>> [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

문자열은 뒤에서부터 처음 해당 문자를 찾은 인덱스를 알아내고 싶을 때 rindex()라는 함수를 사용하면 된다.
리스트에서는 사용할 수 없어서 어떻게 구현하는지 찾아봤는데

c = [1, 3, 5, 7, 5, 8, 9, 10, 5, 6, 4, 3]
위 같은 리스트가 있을 때, 뒤에서 처음 등장하는 5에 해당하는 인덱스를 찾고 싶을 때,
len(c) - c[::-1].index(5) - 1

이렇게 하면 찾을 수 있다.

c = [1, 3, 5, 7, 5, 8, 9, 10, 5, 6, 4, 3]

def listrindex(a, value)
	return len(a) - a[::-1].index(value) - 1
    
print(listrindex(c, 5))

>>> 8

# c[8]에 찾으려는 뒤에서 처음 나오는 5가 있다.

pop(0)과 deque의 popleft()

둘 다 첫 번째 요소를 제거하는 것이라 같은 시간 복잡도가 걸릴 줄 알았는데 시간 복잡도가 O(1)인 pop()과 달리 pop(0)은 시간복잡도 O(n)으로 리스트의 크기에 따라 시간이 오래걸린다고 한다. 뒤에서부터 찾아서 그런듯...?

deque 컨테이너 사용시 popleft() 를 사용하면 O(1)의 시간 복잡도로 리스트의 pop(0)과 같은 기능을 사용할 수 있다.

list와 set, dict 자료형에서 in 연산자의 시간 복잡도

set, dict 자료형에서 in 연산자의 시간 복잡도는 O(1)이지만
list 자료형에서 in 연산자의 시간 복잡도는 O(n)이다.