백준 11003 최솟값 찾기 혼내주기
슬라이딩 윈도우 + pq/deque 문제. 내가 푼 방법은 우선순위 큐에 값과 인덱스를 넣어서 매번 범위에서 벗어난 최솟값을 비우고 유효한 최솟값을 출력하는 방식이었다. 근데 다른 사람들의 풀이를 보니 덱을 이용하면 최대 사이즈를 l개로 유지하면서도 풀 수 있길래 바꿔보았다. 확실히 pq는 범위에서 벗어난 얘들이 큐에 남아서 메모리를 많이 차지하는 반면 덱은 메모리를 반밖에 사용하지 않는다. 생각해보니 pq로 풀면 슬라이딩 윈도우라고 하기도 뭐한 것 같다... 비교 - 아래가 우선순위 큐를 이용한 풀이, 위가 덱을 이용한 풀이 덱 #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, l, ..
혼내주기
2021. 8. 1. 23:04