[Programmers] 2021 카카오 채용연계형 인턴십: 표 편집(Python)/Hashing

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

해싱을 이용한 문제가 종종 나오는 추세인듯 .... ㅠ

실제 코테에서는 뭔가 해싱을 써야되지 않을까?라는 생각만 하고 어려워보여서 다른 문제 풀었었는데 실제로 풀어보니 생각만큼 어렵진 않았다

연습할 때 정확성/효율성이 나뉘어져 있는 문제는 우선 러프하게 정확성만 통과하게 짜본 뒤 효율성 풀이로 고치는 편이다

그래서 이번 문제도 단순 구현으로 푼 뒤 해싱을 이용해서 다시 풀어봤다

 

1. 테이블의 값이 활성화/삭제되었는지 체크할 status 배열을 만든다
2. 특정 레코드가 삭제되면 status 배열에 False로 표시한 뒤 stack에 push한다
3. 특정 레코드가 복구되면 stack에서 pop한 뒤 status 배열을 다시 True로 수정한다

 

이 부분은 동일하고, 이전/다음 레코드를 찾는 과정을 단순 구현 / 해싱으로 나눴다

 

단순 구현 풀이

1. 현재 U/D에서 이동해야 할 회수대로 index를 이동한다
2. 만약 이동 도중 비활성화된 레코드이면 카운트를 하지 않고 활성화된 레코드가 나올 때 까지 이동한다

해싱 풀이

1. pre, post라는 이름의 dictionary를 만든다
   1. pre: 현재 index의 이전 index를 가리킨다
   2. post: 현재 index의 다음 index를 가리킨다
2. 만약 특정 record가 삭제/복구되면 해당 index의 pre, post를 수정한다(연결리스트와 유사하게)

 

딕셔너리가 생각보다 메모리를 많이 차지하지 않아서 pre, post 두 개의 딕셔너리를 이용한 해시 풀이로 효율성을 통과햇당

def solution(n, k, cmd):
    answer = ''
    status=[True for _ in range(n)]
    st=[]
    dy=[-1,1]
    pre=dict()
    post=dict()
    for i in range(n):
      pre[i]=i-1
      post[i]=i+1
    pre[0]=n-1
    post[n-1]=0
    #삭제한 행을 순서대로 넣을 스택

    p=k
    last=n-1

    for c in cmd:
      op=c[0]
      if op=='U':
        cnt=int(c[2:])

        for _ in range(cnt):
          p=pre[p]
      elif op=='D':
        cnt=int(c[2:])

        for _ in range(cnt):
          p=post[p]
      elif op=='C':
        st.append(p)
        status[p]=False

        post[pre[p]]=post[p]
        pre[post[p]]=pre[p]

        if p==last:
          p=pre[p]
          last=p
        else:
          p=post[p]
      else:
        status[st[-1]]=True
        post[pre[st[-1]]]=st[-1]
        pre[post[st[-1]]]=st[-1]

        if st[-1]>last: last=st[-1]
        st.pop()

    for i in status:
      if i: answer+='O'
      else: answer+='X'

    return answer