최솟값 찾기(백준 11003번)

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

11003번: 최솟값 찾기

문제 설명

N개의 수와 L이 주어질 때,  Ai-L+1 ~ Ai수중에서 최소값을 찾는 문제이다. 

N = 12, L = 3 일때, 1 5 2 3 6 2 3 7 3 5 2 6 주어 지면 제일 처음은 1이므로 1 그다음 은 1, 5 중에 1 그 다음은 1, 5, 2 중에 1 그다음은 5,2,3 중에 최소값 2가 출력이 된다.

 

알고리즘 설명

특정한 범위에서 최소값이나 최대값을 구할 때 쓰는 방법중에 슬라이딩 윈도우라는 방법이 있다. 

슬라이딩 윈도우는 2개의 포인터로 범위를 지정한 다음 범위를 유치한 채로 이동하며 문제를 해결해 나가는 것이다.

 

이 문제의 입력값을 보면 최대 5000000개가 존재 할 수 있다. 최소값이므로 정렬 알고리즘을 사용해야 할 거 같은데 정렬 알고리즘은 O(nlogn)이므로 시간초과가 나올 확률이 크다. 그러므로 정렬 알고리즘을 사용하지 않고 최소값을 찾아야한다. 그때 사용하는 방법이 Deque를 이용하는 것이다.

 

Deque에는 value와 index가 저장이 된다.

• 만약 지금 덱에 맨 마지막 value가 현재 추가할 value보다 크면 덱에 맨 마지막 요소는 삭제를 한다.
• 반대로 지금 덱에 맨 마지막 value가 현재 추가할 value보다 작으면 현재 추가할 value를 덱에 추가한다.
• 제일 처음 요소의 index와 마지막 요소의 index의 차가 L이면 제일 처음 요소를 삭제한다.
• 최소값은 덱의 맨 마지막 요소이다.

 

구현

for (int i = 0; i < N; i++) {
    int now = Integer.parseInt(stringTokenizer.nextToken());
    //덱의 마지막 value가 현재 추가할 value보다 클 때 
    while(!dq.isEmpty() && dq.getLast().value > now){
        dq.removeLast();
    }
    //추가
    dq.addLast(new Node(now,i));
    //인덱스 범위가 L보다 커질 경우 검사
    if(dq.getFirst().index <= i-L){
        dq.removeFirst();
    }
    bufferedWriter.write(dq.getFirst().value + " ");
}

 

전체적인 코드

https://github.com/Heron-Woong/CodingTest_Practice/blob/main/%EB%B0%B1%EC%A4%80_11003.java

GitHub - Heron-Woong/CodingTest_Practice