개발 블로그

과거 지원했던 한 회사의 라이브 코딩 테스트에서 나왔던 문제였는데, 제대로 대답하지 못했던 기억이 난다. 다시 풀고 잊지 않기 위해 기록해 둔다. 이 문제의 관건은 결국 최대값과 최소값을 O(1)에 접근하는 것이다. 내가 알고 있는 최대값과 최소값을 가장 빠르게 찾을 수 있는 것은 heap 을 쓰는 것인데 heap을 쓴다고 하더라도 O(logN)이 걸리기 때문에 이 문제를 풀 수 없다. 문제를 푸는 실마리는 count 값이 1씩 증감한다는 것이다. 따라서 count 값이 변경될 때 순서를 알기 위해서 전체 노드를 다 살펴볼 필요 없이 자기자신보다 1 크거나 작은 노드만 살펴보면 된다. 자연스럽게 linked list 를 생각해 볼 수 있다. linked list 는 노드의 추가 삭제가 상수시간에 이뤄지고..