BOJ 11003 최소값 찾기(C++)

최소값 찾기 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
3 초	256 MB	643	188	106	31.832%

문제

N개의 수 A1, A2, ..., AN과 L이 주어진다.

Di = Ai-L+1 ~ Ai 중의 최소값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이 때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

입력

첫째 줄에 N과 L이 주어진다. (1 ≤ L ≤ N ≤ 5,000,000)

둘째 줄에는 N개의 수 Ai가 주어진다. (-109 ≤ Ai ≤ 109)

출력

첫째 줄에 Di를 공백으로 구분하여 순서대로 출력한다.

예제 입력 

12 3
1 5 2 3 6 2 3 7 3 5 2 6

예제 출력 

1 1 1 2 2 2 2 2 3 3 2 2

힌트

출처

• 문제를 만든 사람: baekjoon

알고리즘 분류

• 슬라이딩 윈도우

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include    <stdio.h> #pragma warning (disable:4996) int A[5555555]; int dq[5555555]; int front = 100; int rear = 100;   int main() {     int N, L;     scanf("%d %d", &N, &L);     for (int i = 1; i <= N; ++i)     {         scanf("%d", &A[i]);           if (front == rear) //deque가 비어어져있는 경우 앞에 넣어준다.             dq[--front] = A[i];         else         {             while (front != rear && dq[rear-1] > A[i])                 dq[--rear] = 0;             dq[rear++] = A[i];         }         if (i > L && dq[front] == A[i - L]) dq[front++] = 0;           printf("%d ", dq[front]);     }     return 0; }

dequeue(min heap)를 사용한 문제. 

처음 풀 때는 

최소값을 저장해 두고, 최소값이 여전히 해당 윈도우 내에 있다면 추가되는 값과의 비교만 하면 된다고 생각했는데

최악의 경우를 고려하지 않았다. 최악의 경우 계속 최소값을 다시 찾게 되면 시간초과가 나게 된다. 

N개의 수 중 L개의 범위 내의 최소값이므로 최악의 경우 대략적으로 N*L이 될 수 있다. 

위의 문제는 해당 윈도우 내에 최소값을 다시 찾아야 할 경우를 대비하지 않았다는 것인데, 이를 해결하려면 현재의 최소값 뿐만 아니라

2위값, 3위값 등을 후보 값들을 저장해야 한다. 

이를 min heap을 이용하면 해결하여 연산을 상당히 줄일 수 있다. 

1 5 2 3 6 2 3 7 3 5 2 6이 들어온다고 할 경우 

1을 min heap에 넣어준다. 

5는 1보다 크지만 1과 5중에 2등 후보가 될 수 있다. 넣어준다. - 여전히 min heap이므로 root node는 가장 작은 1이 된다.

2는 1보다 크지만 5보다 작다. 2까지 왔을 때 5는 더이상 어떤 윈도우에서도 후보가 될 수 없게 된다. 때문에 더이상 신경쓰지 않아도 되므로 빼준다.

뺀 후에 2를 넣어준다. 

1 2가 들어있으므로 1이 사라지는 위치가 될 때 자동적으로 2라는 후보(2등)가 root node가 된다. 

3이 들어올 경우 

1, 2보다 크기 때문에 후보가 될 수 있으므로 넣어준다. 

1, 2, 3이 들어가게 되는데 1의 경우 3이 들어올 때 이미 고려하지 않아도 되는 위치가 되므로 제거해준다. 

자연스럽게 2가 최소값이 된다. 

이런 순서로 힙을 이용하게 되면 

삽입, 삭제 하는데 각각 O(logN)이 되므로 

모든 N을 돌며 삽입, 삭제하므로 대략 O(NlogN)의 시간복잡도를 가진다고 할 수 있다.