PS 이야기

두 개의 Priority Queue(heap) 를 이용해서 문제를 해결할 수 있다.하나는 max heap이고 하나는 min heap 이다. heap에 원소의 값과 동시에 index도 같이 pair로 삽입한다.그리고 pop 될 때 해당 index에 visit 체크를 해주고, 최대 최소 값을 구할 때에 이미 visit가 체크된 것은 무시해주면 된다. 이러한 테크닉은 코딩이 편하며, 시간복잡도에 영향이 없다.하지만, 공간 복잡도에는 영향이 있지만 빅오표기법 상으로는 영향이 없다.(Memory sensitive 한 문제에서는 직접 heap를 구현해야할 수도 있다.) 처음에 문제를 각 쿼리마다 최대, 최소 값을 출력해야 되는 문제를 오해하고 생각해 보다 간단한 방법이 존재할 수도 있다. ** 대회 때는 없던 크리..

아직 풀지 못 했다.

한글 문제 부터 순서대로 훑어서 가장 먼저 풀게된 문제다. 처음에 수식으로 문제를 풀려하다가 시간이 오래걸릴 것 같아, $O(N)$에 풀게되었다. 생각은 해보지 않았지만, 분명 더 빠른 방법들도 존재할 것이다. 우선 문제에서 $$ 가 주어진다.이 때 가능한 연도는 $year = k \times N + y \space (0 \le k < M)$ 이다.따라서 k를 0 부터 M-1 까지 돌려보고 $year$ 를 구한 뒤 $x \equiv year (\bmod M)$인 경우가 있으면 그 $year$를 출력하면 되고, 아니면 -1을 출력하면 된다. 자세히 적진 않았지만 modulo 연산을 통해 0이 나오면 M으로 바꿔주는 과정이 필요하다.