[코딩테스트 합격자 되기(기본) 2주차 과제] 리스트/덱/딕셔너리

---

✔ List 메서드 시간복잡도

List 자료구조 메서드의 시간 복잡도

List Method	Time Complex
lst.append(n)	O(1)
lst.insert(idx, n)	O(len(lst))
lst.pop()	O(1)
lst.pop(idx)	O(len(lst))
lst.remove(n)	O(len(lst))
lst.extend(list)	O(len(list))
lst[idx]	O(1)
lst1 + lst2	O(len(lst1) + len(lst2))
n in lst	O(len(lst))
list(set(Iterable))	O(len(Iterable))

빈번하게 리스트의 원소를 탐색해야할때 매번 if a in b 를 사용하면 O(N) 이 여러번 발생되기 때문에 해시 기반으로 이루어져있는 Set() 를 이용하여 O(1) 을 이요영하여 원소를 탐색하는것이 바람직하다.

---

✔deque 메서드의 시간복잡도

Deque Method	Time Complex
deque.append(n)	O(1)
deque.appendleft(n)	O(1)
deque.pop()	O(1)
deque.popleft()	O(1)
deque.rotate(k)	O(k)

양끝의 데이터 삽입, 제거는 O(1) 이지만 중간요소의 데이터 삽입 및 제거는 매우 느리다

---

✔️ Dictionary 메서드의 시간복잡도

Dictionary Method	Time Complex
dict.get(key)	O(1)
dict[key]	O(1)
dict.pop(key)	O(1)
key in dict	O(1)
del dict[key]	O(1)
dict.keys()	O(1)
dict.items()	O(1)
dict.update(dict2)	O(len())

• 시간복잡도와는 관련없는 얘기이지만 dictionary 의 key 에는 mutable 한 값이 올 수 없다.
• 또한, 두개의 딕셔너리를 합쳐 새로운 딕셔너리를 만드는 것을 아래와 같이 UnPack 으로 구현할 수 있다

a={'one': 1, 'two': 2, 'three': 3}
b={'four': 4, 'five': 5, 'six': 6}
c = {**a, **b}
# {'one': 1, 'two': 2, 'three': 3, 'four': 4, 'five': 5, 'six': 6}

---

✔️실전문제

첫번째 문제

Q. 데이터 10000 개를 연속적으로 맨 앞에 삽입하는 연산을 리스트, 덱을 활용한 두가지 버전으로 구현해주세요. 그리고 결과를 시간복잡도 측면에서 분석해주세요

list 사용시

list 를 사욯했을 때의 시간복잡도는 O(N2) 이라고 생각한다. 반복문을 돌면서 lst 라는 배열의 맨앞에 계속 값을 삽입하고 있기 때문에 연속된 메모리주소 라는 특징을 갖는 배열의 특성상 배열의 맨앞 요소를 제외한 모든 요소가 뒤로 한칸씩 밀려 O(N) 이 또 소요하게 된다. 반복문에서 O(N). insert() 에서 O(N) 즉 O(N2) 이 소요될것으로 예상됩니다.

def lst(number):  
    lst = []  
    for integer in range(number):  
        lst.insert(0, integer)  
    return lst  

print(lst(10000))  

deque 사용시

결과적으로 시간복잡도는 O(N) 이라고 생각합니다. deque 은 다음 원소(노드)의 주소를 갖고있는 연결리스트를 사용하기 때문에 queue 의 맨앞에 값을 넣어도 O(1) 이 소요됩니다.

from collections import deque  

def deq(number):  
    queue = deque()  
    for integer in range(number):  
        queue.appendleft(integer)  
    return list(queue)  

print(deq(10000))

두번째 문제

해당 문제는 Dictionary Comprehension 을 사용했다는 점과 zip 함수를 사용했다는 점을 제외하면 볼게없다고 생각합니다.

names = ["이름1", "이름2", "이름3", "이름4", "이름5", "이름6"]  
numbers = ['010-1111-1111', '010-2222-2222', '010-3333-3333', '010-4444-4444', '010-5555-5555', '010-6666-6666']  
entries = {key: value for key, value in zip(names, numbers)}

세번째 문제

Q. 여러 사용자들이 같은 영화에 대해 여러 번 평점을 줄 수 있습니다. 각 평점은 순서대로 기록되어 있어야 하며, 동일한 영화에 대해 여러 사용자가 다양한 평점을 줄 수 있습니다. 당신의 임무는 이 평점들을 순서대로 반환하는 것입니다.

• 요구사항 : 특정 영화에 대한 모든 평점을 반환합니다.

A. 개인적으로 해당문제는 Dictionary 보다 List 가 훨씬 적합한 자료구조라고 생각합니다. 동일한 영화에 대한 평점 이 여러개 있을 수 있고 이는 곧 key 의 중복허용이라는것을 의미하기때문에 key 의 중복 을 허용하지 않는 딕셔너리는 적합하지 않다고 생각합니다.

def solution_list(movie_entries, query):  
    return [movie_entries[idx] for idx, (movie, score) in enumerate(movie_entries) if movie == query]  

def solution_dict(movie_entries, query):  
    table = {}  
    for idx, entry in enumerate(movie_entries):  
        table[idx] = entry  
    return [entry for entry in table.values() if entry[0] == query]  

print(solution_list([('Star Wars', 8), ('Avengers', 9), ('Star Wars', 7), ('Avengers', 8), ('Star Wars', 9)], 'Star Wars'))  
print(solution_dict([('Star Wars', 8), ('Avengers', 9), ('Star Wars', 7), ('Avengers', 8), ('Star Wars', 9)], 'Star Wars'))

---

✔️프로그래머스 문제

리스트

배열 두배 만들기

해당문제의 시간복잡도는 2N (for문 그리고 안에서 ** 연산). 즉 빅오 표기법으로 O(N) 이라고 생각됩니다.

def solution(numbers):  
    return [v*2 for v in numbers]  

print(solution([1,2,3,4,5]))

배열의 유사도

해당문제의 시간복잡도는 O(N2) 라고 생각됩니다. s1, s2 배열(리스트) 모두 맨끝까지 반복문을 돌며 값이 같은지 확인해야 하기 때문에 3N2 (nested for 문, if, += ) 즉 O(N2) 이라고 생각됩니다.

def solution(s1, s2):  
    answer = 0  
    for char in s1:  
        for c in s2:  
            if char == c:  
                answer += 1  
    return answer  

print(solution(["a", "b", "c"], ["com", "b", "d", "p", "c"]))  
print(solution(["n", "omg"], ["m", "dot"]))

진료순서 정하기

해당문제의 시간복잡도는 sorted 로 인해 무조건 NLogN 은 먹고 들어가게 된다. 게다가 리턴되는 리스트 컴프리핸션내부에서는 N * N = N2. 결국 시간복잡도는 O(N2) 이라고 생각된다.

def solution(emergency):  
    sorted_emergency = sorted(emergency, reverse=True)  
    return [sorted_emergency.index(score) + 1 for score in emergency]  

print(solution([3, 76, 24]))  
print(solution([1, 2, 3, 4, 5, 6, 7]))  
print(solution([30, 10, 23, 6, 100]))

딕셔너리

폰켓몬

def solution(nums):
    length = len(nums)
    choice = length // 2
    counter = {}
    for integer in nums:
        counter.setdefault(integer, 0)
        counter[integer] += 1
    kind = sorted(counter.values())
    return min(choice, len(kind))

완주하지 못한 선수

def solution(participant, completion):  
    table = {}  
    for person in participant:  
        table.setdefault(person, 0)  
        table[person] += 1  
    for compl in completion:  
        table[compl] -= 1  
    for key, value in table.items():  
        if value == 1:  
            return key

전화번호 목록

def solution(phone_book):  
    answer = True  
    table = {}  
    for phone in phone_book:  
        table[phone] = 1  
    for phone in phone_book:  
        tmp = ''  
        for integer in phone:  
            tmp += integer  
            if tmp in table and tmp != phone:  
                answer = False  
                break    return answer