[Queue] 배열 구간 최솟값/최댓값 구하기

문제 : https://leetcode.com/problems/sliding-window-maximum/

Sliding Window Maximum - LeetCode

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

11003번: 최솟값 찾기

 

이번에 풀어본 것은 leet코드의 구간 최댓값 찾기이다.

첫번째 풀이방법 

1. 3개씩 구간을 잡는다.
2. 내장함수 max를 이용해 최댓값을 알아낸다.
3. 시간 복잡도 실패 😞 

코드

import Foundation

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var q = [Int]()
        var result = [Int]()
        
        for element in nums {
            if q.count < k {
                q.append(element)
                continue
            }
            
            if q.count == k {
                result.append(q.max()!)
                q.removeFirst()
                q.append(element)
                continue
            }
        }
           result.append(q.max()!)
        return result
    }
}

 

두번째 풀이방법 : Monotonic Queue

 

monotone queue란?

monotone + queue의 합성어로 단조로운 큐라는 뜻이다. 생각할 필요 없는 원소들을 제거하고 큐의 맨앞 원소는 제일 큰 값이 된다. 그전 원소들은 제거 된다.

 

모노톤 큐 만드는법

1. 모노톤 큐의 맨앞부분을 보면서 현재 위치까지 영향력을 줄 수 있을지 없을지(현재 위치의 값보다 작은지 큰지) 확인한다.
2. 모노톤 큐의 뒷 부분을 보면서 현재 넣고자 하는 값보다 모노톤 큐의 맨 뒤에 있는 원소가 크거나(최소값) 작으면(최댓값) 제거한다. 
3. 더 이상 맨뒤에 있는 원소가 현재 넣고자 하는 값보다 크지 않거나(최소값), 클 때(최댓값) 큐가 빌 때까지 2번의 과정을 반복한다.
4. 현재 위치의 값을 넣는다.
5. 큐는 단조 증가(최솟값) or 단조 감소(최댓값)하는 형태이기 때문에 구간내의 최솟값,최댓값은 큐의 가장 앞에 있는 값이다.

출처: https://stonejjun.tistory.com/126 [돌이 코딩하는 방]

 

코드

import Foundation

class Solution {
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        var maxIdx = [Int]()
        var res = [Int]()
        
        for i in 0..<nums.count {
	//1,3번 과정
            while maxIdx.count > 0 && nums[maxIdx.last!] < nums[i] {
		//2번 과정
                maxIdx.removeLast()
            }
            //4번 과정
            maxIdx.append(i)
            
            if i >= k - 1 {
                if maxIdx.first! + k == i {
                    maxIdx.removeFirst()
                } 
                //5번 과정
                res.append(nums[maxIdx.first!])
            }
        }
        
        return res
    }

 

코드만 보면 이해가 잘 안가니 예시를 들어보자면

• nums = [1,2,3] , k = 2 
• i = 0 일 때 maxIdx = [0]
• i = 1 일 때 maxIdx = [1] res = [2]
• i = 2 일 때 maxIdx = [2] res = [2, 3]

흠 그런데 전부 1번째 if 문만 통과하네.. 2번째 if문 까지 걸리는 예시를 알아보자

 

• nums = [5,4,3], k = 2
• i = 0 일 때 maxIdx = [0]
• i = 1 일 때 maxIdx = [0,1] res = [5]
• i = 2 일 때 maxIdx = [1,2] res = [5,4] // 여기서 2번째 if 문이 걸리네
• i = 3 일 때 maxIdx = [2,3] res = [5,4,3] // 여기서도 걸리네

 

중간에 하나 꺼를 바꿔볼까..?

• nums = [5,3,4], k = 2
• i = 0 일 때 maxIdx = [0]
• i = 1 일 때 maxIdx = [0,1] res = [5]
• i = 2 일 때 maxIdx = [2] res = [5, 3] // 2번째 if문 안걸리네 

 

아하..! 이런식이군~!