📚 TIL

📕 알고리즘 강의 3주차

📖 해시

• index 만들기 hash(key) % len(self.items)
• hash('test')%len(array) 값과 hash('slow')%len(array) 의 값이 같은 경우 해시 충돌이 일어남 => 체이닝 : 링크드리스트 사용
  => 충돌이 일어나는 경우 연결리스트로 연결 (key,value) 이 담긴 튜플을 노드에 저장

class LinkedTuple:
    def __init__(self):
        self.items = []

    def add(self, key, value):
        self.items.append((key, value))

    def get(self, key):
        for k, v in self.items:
            if k == key:
                return v
                
class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self.items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)

    def get(self, key):
        index = hash(key) % len(self.items)
        return self.items[index].get(key)

• 개방주소법 : 배열에서 비어있는 자리에 값을 추가

📌 오늘의 문제

✔ 백준 1874 스택수열

N=int(input())

stack=[]
num=1
answer=[]
no_flag=0
for i in range(N):
    now=int(input())
    while num<=now:
        stack.append(num)
        answer.append('+')
        num += 1

    if now==stack[-1]:

        stack.pop()
        answer.append('-')

    else:
        no_flag=1

if no_flag:
    print('NO')
else:
    for i in answer:
        print(i)

30분 정도의 고민끝에 구글링을 하기로 했다.
어떤 경우에 스택수열이 불가능한지를 먼저 생각해내야 했던 것 같다.
현재 수열의 숫자가 나올 때 까지 오름차순으로 push 했는데 stack의 top이 그숫자가 아니면 그것은 스택수열이 불가능이다.
이 과정을 생각해내기가 조금 어려웠다