datastructure

시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 682 178 121 22.787% 문제 송훈이는 로봇 동아리 회원이다. 로봇 동아리에서 필요한 부품이 있을 경우 자유롭게 빌려서 쓰고 다시 돌려놓으면 된다. 하지만 부품 정리를 하다가 부품 관리가 너무 힘들어져 새로운 시스템을 도입하려고 한다. 부품을 빌려갈 경우 부품 대여장에 정보를 반드시 작성해야한다. 또한 빌려간 부품을 반납 할 경우에도 부품 대여장에 정보를 작성해야한다. 또한 대여기간을 정하고 대여기간을 넘길 경우 1분당 벌금을 부여하도록 하는 시스템이다. 만약 대여기간이 5분, 1분당 벌금이 5원이라 했을 때 대여한 시각이 2021년 1월 1일 1시 5분이라면 2021년 1월 1일 1시 10분까지 반납해야한다. 2021년 1월 ..

배열로 무식하게 푸는 방법과 우선순위 큐를 이용해서 푸는 2가지 방법이 있었다. 첫번째로는 배열을 사용한 풀이인데 나는 우선 이것부터 떠올렸다. 매번 값을 받을 때 마다 sort를 해주어서 홀수번 째 마다 중앙값을 구해주면 됐는데 시간초과가 날줄 알았지만 간당간당하게 통과했다. 아무래도 수열의 크기가 크지 않아서 그랬던 듯 하다. 두번째 풀이는 min-heap과 max-heap을 이용한 풀이였다. 이건 다른 분들의 블로그를 참고해서 푼 문제이다. 확실히 배열로 풀었을 때 보다 최적화 면에서 더 나았다. 어떻게 이걸 바로 떠올리고 풀지라는 신기한 생각을 또 가지게 되었다. (__) 1. 중앙값의 개수 출력 => (N+1) / 2 2. 최대힙과 최소힙의 크기가 같다면 최대힙, 다르다면 최소힙에 값을 넣는다...

이중 우선순위 큐 구현 문제였다. min-heap 과 max-heap 두개로 구현해볼까 했는데 뭔가 내가 전혀 모르는 방법이 있을 것 같아서 찾아보니 min-max-heap을 구현하는 방법과 c++의 STL 라이브러리에서 Multiset을 이용한 방법 그리고 내가 사용한 TreeMap을 이용한 구현 방법이 있었다. 먼저 나는 다른 알고리즘 문제를 풀면서 Map 자료구조 중에서는 항상 HashMap 만을 사용해왔었다. TreeMap은 내부가 레드 블랙 트리를 사용하고 있고 삽입, 삭제, 추가 모두 O(log n)의 시간복잡도가 나와서 HashMap 보다는 성능이 떨어진다. 하지만 범위의 검색을 하거나 최댓값, 최솟값을 찾을 때는 TreeMap을 사용하는 것이 효율적이다. 처음에는 구현할 때 중복으로 들어오..

스택을 사용한 문제였다. 어느 부분에 자료구조를 사용해야 하는지 감을 잡을 수 있는 문제이다. 우선 연산자, 피연산자, 괄호의 우선순위를 정해준다. '(', ')' = 0 '-', '+' = 1 '*', '/' = 2 그리고 input으로 주어진 식에서 탐색되는 경우는 4가지 이다. 1. 알파벳 2. 여는 괄호 3. 닫는 괄호 4. 연산자 1번의 경우엔 바로 sb에 append해주면 된다. 2번의 경우엔 바로 stack에 push 해주면 된다. 3번의 경우엔 스택의 top에 여는 괄호가 나올 때 까지 pop을 해서 그 요소를 sb에 append 해주면 된다. 4번의 경우엔 stack의 top에 있는 요소가 현재 연산자보다 높거나 같은 경우 계속해서 pop을 해서 sb에 append 해주면 된다. 그리고 ..