(JAVA) 백준 11003번 : 최솟값 찾기 --- [슬라이딩 윈도우]

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

11003번: 최솟값 찾기

 

안녕하세요.

 

슬라이딩 윈도우 문제입니다.

 

참고로, 정답은 맞는데 시간 초과로 실패했습니다.

 

통과된 코드를 제출해봐도 시간 초과가 떠서 포기했습니다.

 

 

그렇지만 소스코드가 틀리진 않기 때문에 이 문제를 포스팅해보려고 합니다.

 

 

 

*** 슬라이딩 윈도우에 대해 짚고 넘어가고 싶으시면 아래 포스팅을 참고해주시면 감사하겠습니다.

https://maivve.tistory.com/224?category=844319

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

 

 

이 문제는 ArrayDeque 를 사용해서, Window가 3을 유지한 채 배열을 슬라이딩 하면 됩니다.

 

즉, ArrayDeque의 원소 개수는 L개를 유지해야하고,

 

ArrayDeque 에 들어가는 원소는 index 입니다.

 

 

Q. 왜 원소의 값을 넣지 않고 index를 넣느냐?

  ->  i - L + 1 ~ i 의 인덱스 중 최솟값을 찾기 때문에, 해당 범위를 벗어나는 원소는 비교대상에서 제외시켜줘야 하기 때문입니다.

  ->  값이 가장 낮은 원소가 들어가면 아무리 슬라이딩 해도 해당 원소를 제거할 기준이 없기 때문이죠.

 

 

이 부분만 알고나면 해결 매커니즘이 떠오릅니다.

 

 

 

 

매커니즘

---

  1)  Index를 담는 Deque 생성

    *** Deque는 오름차순 으로 사용할 계획입니다.

 

  2)  Deque 내의 i - L + 1 ~ i 인덱스를 벗어나는 원소가 있다면 제거 (pollFirst())

 

  3)  Deque 내에 peekLast() 로 가장 오른쪽에 있는 값을 꺼내보며 Array[i] 의 값과 비교. 그래서, peekLast() 가 더 크면 쓸모없으므로 바로 pollLast() 로 버린다. (더 큰 값이 없을 때 까지 반복)

   *** 여기서 굳이 Deque의 개수를 유지할 필요가 없는게, 몇 개가 들어있든 해당 범위 내 최솟값만 구하면 되기 때문입니다. 

 

  4)  가장 맨 뒤에 인덱스 i 넣기. (add = offer)

 

  5)  peekFirst() 로 가장 맨 왼쪽의 인덱스를 가져와 최솟값을 얻고, 이를 별도 List에 저장.

 

  6)  결과 List 출력 

 

 

이상입니다.

 

감사합니다.

 

 

소스코드

---