[백준] 2075 - N번째 큰 수

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

---

계속 고민한 문제다. 그러다 떠오른 방법이 있는데 괜찮은 방법같았다. 우선 각 열들(column)들의 스택으로 갖게 한다. 그럼 스택의 top은 그 열에서 가장 큰 값들을 갖고 있게 된다. 그리고 각 스택의 top들을 비교해 가장 큰 값을 가진 스택에서 pop을 한다. 이 과정을 N번 반복한다. 그러면 N번째에 pop된게 답이다! 

 

시간복잡도는 O(N^2)으로 끊어진다. 우선 입력된 값들로부터 스택들을 세팅하는데 O(N^2)이다. 그리고 N번에 걸쳐 pop을 하는데, N개의 스택들에 대해 매번 top들의 값을 비교하니까 이것도 O(N^2)이다. 따라서 전체 시간복잡도는 O(N^2).

 

이 논리로 문제를 풀었는데, 틀려버렸다. 메모리제한이 있었다.

 

나 고민 많이 했었는데..

 

N x N 보드의 전체 값들을 저장하면 안된다. 아니 그럼 어케 하징?

 

이건 내가 지금 떠올릴 수 없는 쌈박한 접근방법이 필요하다고 느꼈다. 뭐 그 전에도 잘한 건 아니었지만 알고리즘 문제들에서 눈을 돌린지 너무 시간이 많이 지나서..이건 내가 지금 머리끄댕이 잡고 낑낑대는건 시간낭비라고 생각했다. 마에스트로.. 준비해야 되니까!

 

일단 코드는 다음과 같다.

 

원래는 코드에디터로 코드 쓰는데 요즘 새로 쓰는 폰트가 넘 귀여워서 걍 캡처본으로 대체

 

우선 이 문제는 다음 논리로 해결가능하다.

 

• N개의 값을 보관가능한 박스를 만든다.
• 모든 숫자들을 박스에 넣어볼 것이다.
• 박스에 들어있는 숫자가 N개가 아니면 일단 집어넣는다.
• 박스에 들어있는 숫자가 N개면 박스에 들어있는 숫자 중 제일 작은 값과 지금 넣으려는 숫자를 비교한다
• 지금 넣으려는 숫자가 더 크면 박스에 그 숫자를 넣고, 박스에서 젤 작은 숫자를 뺀다.
• 즉 항상 박스안의 숫자는 N개로 유지되며, 모든 숫자에 대한 작업을 끝내면 가장 큰 N개의 숫자가 들어있다.

 

다만 박스를 그냥 리스트로 만들면 시간복잡도가 너무 커진다. 리스트에서 최솟값 찾는 시간복잡도 = O(N)이고 N^2개들의 숫자에 대해서 작업하니까 전체시간복잡도가 O(N^3)이 됨!

 

이 떄 우선순위 큐를 쓰면 쉽게 해결가능해진다.우선순위 큐! 어떤 목록으로부터 항상 작은 값들을 가져오고 싶거나 항상 큰 값을 가져오고 싶거나..뭐 그럴 때 쓰던 놈이다. push, pop모두 log n 만큼의 시간이 걸린다! 따라서 이 문제를 해결 가능.

 

고정된 사이즈의 자료구조를 만들고 활용하는 테크닉.. 꼭 기억하자.