문제 링크
문제
N*N개의 수가 주어질 때 N번째 큰 수를 구하는 문제이다.
특징으로는 2차원 배열상에서 자신의 한 칸 위에 있는 수보다는 크다는 것이다.
풀이
삽질(메모리 초과)
한 칸 위에 있는 수보다는 크다는 것이 포인트인데, 도대체 어떻게 해야할 지 감이 안 잡혔다.
최대 1500*1500개의 수를 정렬해야하므로 모든 숫자를 정렬하는 것이 아니라는 건 알 수 있다.
결국 문제 분류가 우선순위 큐라는 것을 봐버렸다.(고의 아님ㅋ)
우선순위 큐를 어떻게 활용해야할지 고민하다가 방법이 하나 떠올랐다.
1. 모든 수를 위의 문제 보기처럼 2차원 배열로 저장한 뒤, 각 세로줄을 하나의 list로 관리한다.
2. 초기에 우선순위 큐에 맨 마지막 줄 N개의 수를 저장한다.
3. 가장 큰 수를 제거한 뒤, 해당 수가 있던 list의 마지막 값을 다시 큐에 넣고 list에서 삭제한다.
즉 각 list는 정렬상태를 보장한다.
만약 마지막 줄에서 가장 큰 수 하나를 뺐을 때, 남은 수들 중 가장 큰 수일 확률이 있는 것은 빠진 숫자가 있던 list에서 해당 수 전에 있는 숫자이다.
실버2주제에 이렇게 구현이 복잡하다고? 라는 생각을 하면서 꾸역꾸역 코드를 짰다. list.getLast()같은 메서드도 java11에는 적용이 안 돼서 진흙탕코드를 짜냈다.
결과는 메모리 초과. 항복선언하고 풀이를 찾아봤다.
정답 풀이
메모리 초과가 의미하는 것은 모든 수를 저장하는 것이 방법이 아니라는 것이다.
N번째 큰 수를 찾는 것이고, 작은 수부터 차례로 제거했을 때 N번째 큰 수는 마지막 줄에서 알 수 있다.
즉 우선순위 큐에 총 N개의 수만 유지한 채로 새로운 수를 넣고 가장 작은 수를 빼는 과정을 반복한다. 바로 위에 있는 수보다 더 큰 수라는 특징이 더 뒤에 나오는 수가 N번째 큰 수일 것이라는 사실을 보장해준다.
주의할 점은 큐에서 제거하는 것과 큐에 새로운 수를 넣는 순서이다. 새로운 수를 먼저 넣고 큐에서 제거해야하는데 이 점을 간과했다.
배운 점
문제 난이도가 낮다고 가벼운 마음으로 봤는데, 어려웠다. 접근법을 못 찾으면 쉬운 문제도 어렵게 느끼게 된다. 큐에 데이터를 넣고 빼는 순서도 잘 생각해보고 설계해야한다는 것을 알았다. 삽질한 만큼 배워가는 게 있는 문제이다.
