2075 N번째 큰 수 / c++ / Silver3 / 21분
문제 및 코드
접근 방식
정렬
- 처음엔 그냥 다 받아서 정렬을 한번 하고, N번째 수를 반환하면 되지 않을까 생각했다.
- 그런데 N이 1500이다보니, NN 이면 15001500 = 2,250,000 개의 숫자를 저장해야한다.
- 하나의 숫자는 -10억 ~ 10억이므로, int 자료형이면 충분하고, 그럼 4Byte * 2,250,000 = 9’000’000 Byte 가 필요하다. 이는 다시 9’000 KB이고 9MB 이다.
- 문제의 메모리 제한인 12MB에는 충족했지만, 효율적인 방법이 없을까 생각했다.
- 보통 이런 문제는 마지막 N번째 큰 수를 반환하므로 제일 큰 수부터 N개까지만 숫자를 저장하면 된다.
- 그래서 처음 N개를 받은 뒤, 새롭게 들어오는 입력에 대해서는, 기존 N개의 최소값과 비교하여 그보다 클 경우, 교체해주는 방식을 사용했다.
- 이 때, 탐색 효율을 높이기 위해 upper_bound 를 사용하여 교체할 범위를 찾아서 교체했다. (삭제의 경우 항상 가장 앞 원소가 삭제됨)
- 이렇게 풀고 나니, 기존에 브루트포스로 풀었을 때보다, 메모리 효율은 5배 좋아졌고, 시간 효율은 100ms 좋아졌다.
다시 생각해 볼 점
- 숫자가 N개만 필요하다는 점을 떠올리고 효율적인 코드를 짤 수 있어서 좋았다.
- 그런데, 풀고 나서 알고리즘 분류를 확인해보니 우선순위 큐가 있었다.
- 예전에 코딩 테스트를 한참 연습할 때는 아마 이 문제를 보고 바로 우선순위 큐를 쓰려고 생각했을 것 같다. 그런데, 6개월만에 다시 풀려니 우선순위 큐가 생각나지 않아서 내가 직접 알고리즘을 구현해서 풀었다는게 약간 아쉬웠다. 우선순위 큐를 썼다면 훨씬 빨리 풀었을 텐데..
- 하지만 우선순위 큐를 사용해서 다시 풀어봤는데 시간효율이나 메모리효율은 내가 직접 구현한 것과 정말 근소한 차이를 보여줘서 그나마 위안이 되었다.
- 다음에는 이처럼 정렬과 관련되고, 그 때 그 때 pop이 필요한 문제가 있다면 우선순위 큐를 염두해둬야겠다.
