coding-test-python
3주차: 스택, 큐, 해쉬
3주차
스택
한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료구조
- push(data) : 맨 앞에 데이터 넣기
- pop() : 맨 앞에 데이터 뽑기
- peek() : 맨 앞에 데이터 보기
- isEmpty() : 스택이 비었는지 확인하기
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, value):
new_node = Node(value)
if self.head == None:
self.head = new_node
return new_node.data
new_node.next = self.head
self.head = new_node
return new_node.data
# pop 기능 구현
def pop(self):
# cur = self.head
# cur_next = cur.next
#
# self.head.next = None
#
# self.head = cur_next
#
# return cur.data # 마지막 데이터 반환
if self.is_empty():
return "Stack is Empty"
delete_head = self.head
self.head = self.head.next
return delete_head
def peek(self):
if self.is_empty():
return "Stack is empty!"
return self.head.data
# isEmpty 기능 구현
def is_empty(self):
return self.head is None
큐
실제로 코딩테스트에서 큐를 사용할 때는 collections.deque 를 사용해야 한다.
from collections import deque
queue = deque()
queue.append(3) # enqueue
queue.popleft() # dequeue
class Node:
def __init__(self, data):
self.data = data
self.next = None
class Queue:
def __init__(self):
self.head = None
self.tail = None
def enqueue(self, value):
new_node = Node(value)
if self.head == None:
self.head = self.tail = new_node
return new_node.data
else:
self.tail.next = new_node
self.tail = new_node
return new_node.data
def dequeue(self):
if self.is_empty():
return print("현재 큐가 비어있습니다.")
deleted_node = self.head
self.head = self.head.next
deleted_node.next = None
return deleted_node.data
def peek(self):
if self.is_empty():
return print("현재 큐가 비어있습니다.")
return self.head.data
def is_empty(self):
return self.head == None
🤚해쉬
자바스크립트 객체같은 구조, 데이터의 검색과 저장이 매우 빠르다
해쉬 함수를 이용해 키에 대한 숫자를 만들고 이 숫자를 배열 길이로 나누어서 인덱스를 생성하는 방식이다.
index = hash(key) % len(배열)
배열[index] = value
그런데 이렇게 되면 해쉬의 값이 같거나 index의 값이 똑같이 만들어질 경우 충돌이 발생한다.
1. 충돌 방지 - Chaning
이 문제를 해결하는 첫 번째 방법이 링크드 리스트를 이용한 Chaning 기법이다.
배열 안에 각각 링크드 리스트를 넣어둔 형태인데 쉽게 말해서 2차원 배열이라고 보면 된다.
import java.util.ArrayList;
import java.util.List;
class DictChaining {
static class LinkedTuple {
private List<KeyValuePair> items;
public LinkedTuple() {
this.items = new ArrayList<>();
}
public void add(String key, Object value) {
this.items.add(new KeyValuePair(key, value)); // ["333", 7] -> ["77", 6]
}
public Object get(String key) {
for (KeyValuePair pair : items) {
if (pair.key.equals(key)) {
return pair.value;
}
}
return null;
}
static class KeyValuePair {
String key;
Object value;
public KeyValuePair(String key, Object value) {
this.key = key;
this.value = value;
}
}
}
public static void main(String[] args) {
LinkedTuple linkedTuple = new LinkedTuple();
linkedTuple.add("333", 7);
linkedTuple.add("77", 6);
System.out.println(linkedTuple.get("333"));
}
}
| Stack | Queue | Hash Table | |
|---|---|---|---|
| 특정 원소 조회 | O(N) | O(N) | Ω(1) |
| 중간에 삽입 삭제 | O(N) | O(N) | Ω(1) |
| 데이터 추가 | O(1) | O(1) | Ω(1) |
| 정리 | 가장 최근에 들어온 순서대로 처리되어야 하는 일에 필요하다. → Ctrl Z | 들어온 순서대로 처리되어야 하는 일에 필요하다. → 줄서서 받아먹는 경우 | 해시 충돌이 잘 안 일어날 수 있는 상황에서는 매우 좋다. 따라서 해시 함수가 잘 데이터를 흩뿌려줄 수 있는 걸 골라야 한다. |
2. 충돌 방지 - 남는 공간에 넣기
all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]
# 반복문
def get_absent_student(all_array, present_array):
result = []
for x in all_array:
exist = False
for y in present_array:
if x == y
break
if exist = False:
result.append(x)
return result
# 딕셔너리 사용
def get_absent_student(all_array, present_array):
dict = {}
for key in all_array:
dict[key] = True # 아무 값이나 넣어도 상관 없습니다! 여기서는 키가 중요한거니까요
for key in present_array: # dict에서 key 를 하나씩 없앱니다
del dict[key]
for key in dict.keys(): # key 중에 하나를 바로 반환합니다! 한 명 밖에 없으니 이렇게 해도 괜찮습니다.
return key
print(get_absent_student(all_students, present_students))
print("정답 = 예지 / 현재 풀이 값 = ",get_absent_student(["류진","예지","채령","리아","유나"],["리아","류진","채령","유나"]))
print("정답 = RM / 현재 풀이 값 = ",get_absent_student(["정국","진","뷔","슈가","지민","RM"],["뷔","정국","지민","진","슈가"]))