<div id="readability-page-1" class="page"><article id="mainContent">
                                <div>
                                    <p><a href="/m/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98"><span>프로그래밍/알고리즘</span></a></p><h3>LeetCode 23.08.16 : Sliding Window Maximum</h3>
                                </div>
                                <p><cite>Doublsb</cite>
                                    <span> 2023. 8. 17. 01:25</span>
                                </p>
                                                <div>
                                <p data-ke-size="size16"><a href="https://leetcode.com/problems/sliding-window-maximum/" target="_blank" rel="noopener">https://leetcode.com/problems/sliding-window-maximum/</a></p>

<h3 data-ke-size="size23">풀이</h3>
<p data-ke-size="size16">- 보자마자 이중 for문? 생각했지만 제한조건에 nums.length가 10의 5승인 걸 보고 그만둠.</p>
<p data-ke-size="size16">- 우선순위 큐로 최초 k 사이즈만큼의 num들을 정렬해놓고, 다음 k + index에 위치한 숫자를 EnQueue하는 방식으로 생각.</p>
<p data-ke-size="size16">- 우선순위 큐 검색 도중 window 안에 들어와있는 값이 아니면 삭제해보도록 하자.</p>
<p data-ke-size="size16">- 닷넷에는 이미 구현된 <a href="https://learn.microsoft.com/ko-kr/dotnet/api/system.collections.generic.priorityqueue-2?view=net-7.0" target="_blank" rel="noopener">PriorityQueue</a>가 있다.</p>

<pre id="code_1692202769925" data-ke-language="csharp" data-ke-type="codeblock"><code>public class IntMaxCompare : IComparer&lt;int&gt;
{
	public int Compare(int x, int y) =&gt; y.CompareTo(x);
}
        
static int[] Solution(int[] nums, int k)
{
	if (k == 1)
		return nums;
            
	var result = new int[nums.Length - k + 1];

	var queue = new PriorityQueue&lt;int, int&gt;(new IntMaxCompare());
	for (int i = 0; i &lt; k; i++)
		queue.Enqueue(i, nums[i]);

	for (int i = k; i &lt;= nums.Length; i++)
 	{
		int maxIdx = queue.Peek();
		while (maxIdx &lt;= i - k - 1)
		{
  			queue.Dequeue();
			maxIdx = queue.Peek();
		}
                
		result[i - k] = nums[maxIdx];
                
		if(i == nums.Length)
			break;
                
		queue.Enqueue(i, nums[i]);
	}

	return result;
}</code></pre>

<h3 data-ke-size="size23">결과</h3>
<p data-ke-size="size16">Runtime 436 ms (상위 40.53%)</p>
<p data-ke-size="size16">Memory 61.8 MB (상위 32.54%)</p>


<h3 data-ke-size="size23">피드백</h3>
<p data-ke-size="size16">첫 개시 일일 문제가 Hard 난이도라서 당황했는데, 안정적으로 금방 해결해서 다행인 듯.</p>
<p data-ke-size="size16">PriorityQueue 지원 때문에 .Net 7.0 SDK를 설치하느라 괜히 더 걸렸다 (...)</p>
            
            
                </div>


<ins data-ad-client="ca-pub-9527582522912841" data-ad-slot="3250933968" data-ad-format="auto" data-full-width-responsive="true" data-ad-type="inventory"></ins>


                                

                            </article></div>

쌍쌍뱌 작업실

https://leetcode.com/problems/sliding-window-maximum/
 
풀이
- 보자마자 이중 for문? 생각했지만 제한조건에 nums.length가 10의 5승인 걸 보고 그만둠.
- 우선순위 큐로 최초 k 사이즈만큼의 num들을 정렬해놓고, 다음 k + index에 위치한 숫자를 EnQueue하는 방식으로 생각.
- 우선순위 큐 검색 도중 window 안에 들어와있는 값이 아니면 삭제해보도록 하자.
- 닷넷에는 이미 구현된 PriorityQueue가 있다.
 
public class IntMaxCompare : IComparer<int>
{
	public int Compare(int x, int y) => y.CompareTo(x);
}
        
static int[] Solution(int[] nums, int k)
{
	if (k == 1)
		return nums;
            
	var result = new int[nums.Length - k + 1];
	var queue = new PriorityQueue<int, int>(new IntMaxCompare());
	for (int i = 0; i < k; i++)
		queue.Enqueue(i, nums[i]);
	for (int i = k; i <= nums.Length; i++)
 	{
		int maxIdx = queue.Peek();
		while (maxIdx <= i - k - 1)
		{
  			queue.Dequeue();
			maxIdx = queue.Peek();
		}
                
		result[i - k] = nums[maxIdx];
                
		if(i == nums.Length)
			break;
                
		queue.Enqueue(i, nums[i]);
	}
	return result;
}
 
결과
Runtime 436 ms (상위 40.53%)
Memory 61.8 MB (상위 32.54%)
 
 
피드백
첫 개시 일일 문제가 Hard 난이도라서 당황했는데, 안정적으로 금방 해결해서 다행인 듯.
PriorityQueue 지원 때문에 .Net 7.0 SDK를 설치하느라 괜히 더 걸렸다 (...)

LeetCode 23.08.16 : Sliding Window Maximum

댓글