(JAVA) 백준 2075번 : N번 째 큰 수 --- [슬라이딩 윈도우]

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

2075번: N번째 큰 수

 

안녕하세요.

 

이 문제는 우선순위 큐를 활용한 슬라이딩 윈도우 문제 입니다.

 

 

보통 슬라이딩 윈도우 == 투포인터 라고 생각하시는데, 반은 맞고 반은 틀립니다.

 

투 포인터와 슬라이딩 윈도우는 배열의 처음부터 순차적으로 탐색하고 부분 배열을 꺼내보는 것은 같습니다만

 

투 포인터는 부분 배열의 길이가 가변적(늘었다 줄었다) 이지만

슬라이딩 윈도우는 부분 배열의 길이가 고정적(일정) 입니다.

 

 

그렇기 때문에, 문제 유형과 풀이 매커니즘을 파악해서 경우에 맞게 알고리즘을 활용하면 됩니다.

 

 

이 문제는 N 번째로 큰 수를 구하는 문제입니다. 

그런데 입력은 N * N 배열 이 주어집니다.

 

물론 이것만 해당되서 슬라이딩 윈도우를 사용하는 것이 아니라

 

결정적인 이유는 N 번째로 큰 수 를 구하기 때문에, 

 

N 의 크기를 갖는 우선순위 큐를 활용해서

모든 배열을 탐색한 후 poll() 한 번으로 N 번째로 큰 수를 얻을 수 있기 때문입니다.

 

 

탐색 후 끝까지 남아있는 원소들은 N * N 배열에서 가장 짱짱 큰 원소가 1순위 ~ N순위 까지 들어있기 때문에

이는 곧 1 ~ N 번째로 큰 수 와 같은 의미로 보시면 됩니다.

 

 

우선순위 큐는 Queue 이기 때문에, 고정 길이가 아니지 않느냐?

  ->  하나씩 원소 탐색할 때 마다 size 체크하면 됩니다.

 

*** 처음에는 이렇게 구현했는데, 속도 감소를 위해 처음 한 줄을 아예 우선순위 큐에 넣고 진행했습니다.

그래서 다음 줄부터 원소 하나하나 탐색할 때 우선순위 큐에 들어있는 최솟값(peek) 보다 원소의 값이 더 작으면 

poll() -> offer() 을 통해 하나 빼고 하나 넣는 방식으로 size를 유지했습니다.

 

 

 

위에 적은 것을 참고하면 풀이 매커니즘을 만들 수 있습니다.

 

 

이상입니다.

 

감사합니다!

 

 

소스코드

---