[코딩테스트] 리스트/덱(deque)

리스트/덱(deque)

 
이번 시간에는 리스트와 덱(deque, 데크)에 대해 정리해 보겠습니다. 저자님의 스터디 가이드를 참고했습니다. 배열에 대해서는 정리를 한번 했었는데요. 이번에는 리스트의 메서드와 시간복잡도에 대해 알아보겠습니다.

배열 메서드

---

append(item)
- 리스트의 끝에 item을 추가 / 반환 값 없음.
- 기존 원소에 영향을 주지 않기 때문에 시간복잡도 O(1)
 
pop()
- 리스트 맨 끝의 item을 삭제 / 반환 값은 삭제한 원소
- 기존 원소에 영향을 주지 않기 때문에 시간복잡도 O(1)
 
pop(0)
- 리스트 맨 앞의 item을 삭제 / 반환 값은 삭제한 원소
- 맨 앞의 원소를 삭제하면 모든 원소가 한 칸씩 앞으로 이동해야 하므로, 시간 복잡도 O(N), N은 리스트의 길이
- 비효율적
- 맨 앞의 원소를 삭제하는 경우에는 시간복잡도가 O(1)인 deque(덱)을 활용하는 것이 좋음.
 
remove(item)
- 리스트에서 "맨 처음 나오는" item 삭제 / 반환 값 없음
- 시간복잡도 O(N), N은 리스트의 길이
- 비효율적

lst = [1, 3, 11, 7, 11]
lst.remove(11)
print(lst) # [1, 3, 7, 11]

 
extend(K)
- 리스트의 뒤에 list K의 모든 요소를 추가 / 반환 값 없음
- 시간 복잡도는 O(K), K는 리스트 K의 길이
- O(K)는 O(1)이 아니다. K는 변수이므로 정의하기 나름

lst = [1, 2, 3]
lst.extend([7, 8])
print(lst) # [1, 2, 3, 7, 8]

 
item in 리스트
- 리스트에 item 값이 있는지 확인.
- 리스트에 item이 있으면 True, 없으면 False 반환
- 리스트 전체를 순회하면서 값이 있는지 찾는 것이기 때문에 시간복잡도 O(N), N은 리스트의 길이
- 비효율적

lst = [1, 2, 3]
print(3 in lst) # True
print(5 in lst) # False

 
list(set)
- 집합을 리스트로 변환하여 중복을 제거. 순서는 보장되지 않음
- 중복이 있는지 확인해야 하므로 시간복잡도는 O(N)

print(list(set([1, 2, 2, 3, 3, 4]))) # [1, 2, 3, 4]

 

Deque

---

deque에 대해서 더 알아보겠습니다.
deque는 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형입니다.
아래 예시에서도 볼 수 있듯이, 리스트 맨 앞에 원소를 추가, 삭제하더라도 시간 복잡도가 O(1)입니다.
이때 사용하는 메서드는 다음과 같습니다.

• appendleft(x): 데크 왼쪽에 x 추가
• popleft(): 데크 왼쪽에서 요소를 제거

from collections import deque

# 데크 객체 생성
deq = deque()

# append(item): 데크의 오른쪽 끝에 item을 추가합니다.
# 반환값: 없음
# 시간 복잡도: O(1)
deq.append(1)  # 현재 데크: deque([1])
print(deq)  # 출력: deque([1])

# appendleft(item): 데크의 왼쪽 끝에 item을 추가합니다.
# 반환값: 없음
# 시간 복잡도: O(1)
deq.appendleft(0)  # 현재 데크: deque([0, 1])
print(deq)  # 출력: deque([0, 1])

# popleft(): 데크의 왼쪽 끝 요소를 제거하고 그 요소를 반환합니다.
# 반환값: 제거된 요소
# 시간 복잡도: O(1)
deq.popleft()  # 현재 데크: deque([1])
print(deq)  # 출력: deque([1])

# deq[K]: 데크의 K번째 요소를 반환합니다.
# 반환값: K번째 요소
# 시간 복잡도: O(1)
print(deq[0])  # 출력: 1

추가로 참고한 자료입니다.
🔍 앞뒤에서 자료를 넣고 빼려면? ― collections.deque
🔍 리스트 자료형

 

문제 풀이

---

관련 문제를 풀어보겠습니다.

문제 1.

def solution(numbers):
    answer = []
    for i in numbers:
        answer.append(i*2)
    return answer

#간단한 풀이
def solution(numbers):
    return [num*2 for num in numbers]

리스트를 순회하므로 시간복잡도는 O(N)

---

문제 2.

def solution(s1, s2):
    answer = 0

    for i in s1:
        for s in s2:
            if i == s:
                answer += 1
    return answer
    
#간단한 풀이
def solution(s1, s2):
	return len(set(s1)&set(s2));

중첩 반복문의 경우에 시간복잡도는 O(N^2)

---

문제 3.

💡정렬 HOW TO
파이썬 리스트에는 리스트를 제자리에서(in-place) 수정하는 내장 list.sort() 메서드와 이터러블로부터 새로운 정렬된 리스트를 만드는 sorted() 내장 함수가 있습니다.

def solution(emergency):
    answer = []
    s = sorted(emergency, reverse = True)
    for item in emergency:
        answer.append(s.index(item) + 1)
    return answer

💡 정렬의 시간복잡도
emergency의 길이가 N, 정렬할 때의 시간복잡도는 O(NlogN)

이상으로 리스트와 deque에 대해 알아보았습니다.