Sliding Window Maximum (1) 썸네일형 리스트형 239 Sliding Window Maximum 주어진 배열에서 window를 한 칸씩 옯겨가며 window의 최대 원소를 반환하는 문제이다. 입력이 크기 때문에 문제 이름대로 sliding window 방식으로 풀면 당연히 시간 초과가 나버린다. 그래서 이 문제에서는 앞, 뒤로 push, pop 연산을 수행할 수 있는 deque를 사용해야한다. deque로 배열을 순회하며 새로운 원소들을 넣어주는 데, 이때 새로 집어넣어 줄 원소가 deque의 원소보다 크면 deque를 완전히 비워준다. 그리고 deque에는 매번 window로 참조하지 않는 원소가 포함되면 그것도 빼주어야 하고 이를 위해 deque에는 배열의 인덱스를 넣어준다. 말로 적으면 간단하지만 첨할 때는 예외 처리에서 빼먹은 거 찾는 거에서 막혀서 첨에는 deque로 풀려다가 접고 이진트리.. 이전 1 다음
