[Algorithm] 리스트와 딕셔너리

알고리즘 문제를 풀다보면 리스트를 사용했는데 시간초과가 발생하는 경우가 있다.

input을 sys.stdin.readline으로 바꿔봐도 시간초과가 난다.

이런 경우 리스트 말고 다른 방법을 찾아봐야 할 것이다.

---

1. 리스트

리스트란, 대괄호 사이에 쉼표로 구분된 값(항목)들의 목록이다.

쉽게 말해 서로 다른(대부분은 같은) 자료형을 포함하는 목록이라고 생각하면 된다.

arr = [1, 2, 3, 4]

# 1, 2, 3, 4로 이루어진 list

파이썬은 list에 대해 여러가지 연산을 제공해준다.

1.1 리스트 연산의 시간 복잡도

연산	설명		시간 복잡도
len(arr)	arr의 길이		O(1)
arr[i]	i에 해당하는 value		O(1)
arr[i:j]	i부터 j까지 슬라이싱		O(슬라이스하는 길이)
item in arr	arr에 item이 있는가		O(n)
arr.count(item)	arr에 item이라는 값이 몇 개 있는가		O(n)
arr.index(item)	item의 index		O(n)
arr.pop(0)	index가 0인 요소를 제거		O(n)
arr.pop()	마지막 요소를 제거		O(1)
arr.append(item)	arr의 마지막에 item 추가		O(1)
arr.sort()	arr을 정렬		O(nlogn)
min(arr), max(arr)	arr의 최대, 최소값 반환		O(n)
arr.reverse()	arr 반전		O(n)

다양한 연산이 제공되지만 대부분 연산의 시간 복잡도가 O(n)인 것을 알 수 있다.

예를 들어, item in arr의 경우 arr에 item이 있는지 확인하기 위해 arr을 전체 탐색하기 때문에 시간 복잡도가 O(n)이 된다.

2. 딕셔너리

딕셔너리란, (한 딕셔너리 안에서) 키가 중복되지 않는다는 제약 조건을 가진 키:값 쌍의 집합이다.

dict = {1:"hello", 2:"bye"}

# 1:"hello"와 2:"bye"라는 key:value 쌍의 집합

2.2 딕셔너리 연산의 시간 복잡도

딕셔너리에도 사용할 수 있는 여러 연산들이 존재한다.

연산	설명		시간 복잡도
len(dict)	dict의 길이 반환		O(1)
dict[key]	dict에서 key에 해당하는 value 반환		O(1)
dict[a] = b	dict에 a: b 추가		O(1)
key in dict	dict에 key가 있는지		O(1)
dict.pop(key)	dict에서 key에 해당하는 key: value쌍 제거		O(1)

딕셔너리의 경우 연산이 O(1)이다.

3. 결론

리스트와 딕셔너리 중 어느 것을 선택해야 하는지는 상황에 따라 다르다.

딕셔너리의 시간 복잡도가 낮으니 무조건 딕셔너리를 사용하는 것은 잘못된 발상이다.

문제 상황에 맞게 적절한 자료형을 선택해야 한다.

예를 들어, 순서가 있거나 index가 중요한 경우는 list를 사용하고 요소의 포함 여부, 탐색 등이 중요한 경우라면 딕셔너리를 사용하면 되는 것이다.

4. 예시

1620번: 나는야 포켓몬 마스터 이다솜 (acmicpc.net)

1620번: 나는야 포켓몬 마스터 이다솜

위의 문제는 list를 사용하면 시간초과가 발생한다.

문제에서 배열의 최대 길이는 100,000인데 배열을 사용하게 되면 시간 복잡도가 상당히 증가하기 때문이다.

문제에서 가장 중요한 포인트는 첫 부분에서 포켓몬의 이름을 입력 받고, 이후 입력에 해당하는 포켓몬의 이름 또는 포켓몬 번호를 찾는 것이다.

배열을 사용하게 되면, 최대 100,000 길이의 배열에서 100,000번의 index 연산을 해야한다.

이 문제는 여러개의 입력에서 특정 입력을 탐색하는 것이기 때문에 딕셔너리를 이용해야 한다.

최대 100,000 길이의 딕셔너리라 하더라도 특정 key를 갖는 쌍을 찾는 것의 시간 복잡도는 O(1)이기 때문이다.

(딕셔너리만 사용한다고 해결되지는 않고 처음 포켓몬 이름을 입력 받을 때 sys.stdin.readline()까지 해줘야 시간초과가 발생하지 않는다...)