C++로 크기 k인 모든 윈도우에서 첫 번째 음수 찾기

이 문제에서는 N개의 정수로 구성된 배열 arr[]와 크기가 k인 윈도우(창)가 주어집니다. 우리의 과제는 크기 k인 모든 윈도우에서 첫 번째 음의 정수를 찾는 프로그램을 작성하는 것입니다. 해당 윈도우에 음수가 존재하면 그 첫 번째 음수를 출력하고, 존재하지 않으면 음수가 없음을 의미하는 0을 출력합니다.

문제 이해를 위한 예시

입력: arr[] = {-2, 2, -1, 4, 3, -6}, k = 2
출력: -2, -1, -1, 0, -6

설명 −

윈도우 크기 k = 2일 때,
{-2, 2} → 첫 번째 음수는 -2
{2, -1} → 첫 번째 음수는 -1
{-1, 4} → 첫 번째 음수는 -1
{4, 3} → 첫 번째 음수 없음 → 0 출력
{3, -6} → 첫 번째 음수는 -6

해결 방법 1: 브루트 포스(Brute Force)

이 문제를 해결하는 가장 간단한 방법은 배열 arr[]를 순회하면서 크기 k의 윈도우를 만들고, 각 윈도우 내에서 첫 번째 음의 정수를 찾아 출력하는 것입니다.

이 방식은 두 개의 중첩 루프를 사용하기 때문에 시간 복잡도는 O(n*k)입니다. 배열의 크기가 커지면 비효율적일 수 있지만, 문제의 동작 원리를 이해하기에는 가장 직관적인 접근법입니다.

예제 코드

#include <iostream>
using namespace std;

void findFirstNegIntWindowK(int arr[], int n, int k){
   bool negFound;
   for (int i = 0; i<(n-k+1); i++)
   {
      negFound = false;
      for (int j = 0; j<k; j++)
      {
         if (arr[i+j] < 0)
         {
            cout<<arr[i+j]<<"\t";
            negFound = true;
            break;
         }
      }
      if (!negFound)
         cout<<"0\t";
   }
}

int main(){
   int arr[] = {-2, 2, -1, 4, 3, -6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"크기가 "<<k<<"인 각 윈도우의 첫 번째 음수:\n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

출력 결과

크기가 2인 각 윈도우의 첫 번째 음수:
-2 -1 -1 0 -6

해결 방법 2: 슬라이딩 윈도우와 덱(Deque) 활용

더 효율적인 방법은 슬라이딩 윈도우(sliding window) 기법과 유사한 개념을 사용하는 것입니다. 이 방법에서는 크기 k의 윈도우에 포함된 요소들의 인덱스를 저장하기 위해 덱(deque, 양방향 큐)을 생성합니다.

배열을 처음부터 순회하며 크기 k의 덱을 채운 후, 배열의 각 요소마다 덱의 앞쪽에서 하나를 제거하고 뒤쪽에 새로운 요소를 추가하며 윈도우를 한 칸씩 밀어 나갑니다. 슬라이드된 각 윈도우에 대해 첫 번째 음수를 찾아 출력합니다.

음수를 찾는 핵심 로직은 다음과 같습니다. 제거되는 요소가 현재 윈도우의 첫 번째 음수였는지 확인하고, 그렇다면 다음 음수 후보를 찾기 위해 덱의 다음 요소들을 검사합니다. 덱에는 음수의 인덱스만 저장되므로, 덱의 front에 있는 값이 항상 현재 윈도우의 첫 번째 음수가 됩니다. 이를 통해 시간 복잡도를 O(n)으로 개선할 수 있습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

void findFirstNegIntWindowK(int arr[], int n, int k){
   deque<int> windowKsize;
   int i = 0;
   // 첫 번째 윈도우에서 음수 인덱스 저장
   for (; i < k; i++)
      if (arr[i] < 0)
         windowKsize.push_back(i);
   // 윈도우를 한 칸씩 이동하며 처리
   for (; i < n; i++){
      if (!windowKsize.empty())
         cout<<arr[windowKsize.front()]<<"\t";
      else
         cout<<"0\t";
      // 윈도우 범위를 벗어난 인덱스 제거
      while ((!windowKsize.empty()) && windowKsize.front() < (i - k + 1))
         windowKsize.pop_front();
      // 새로 들어온 요소가 음수면 저장
      if (arr[i] < 0)
         windowKsize.push_back(i);
   }
   // 마지막 윈도우 처리
   if (!windowKsize.empty())
      cout<<arr[windowKsize.front()]<<" \t";
   else
      cout<<"0\t";
}

int main(){
   int arr[] = {-2, 2, -1, 4, 3, -6};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 2;
   cout<<"크기가 "<<k<<"인 각 윈도우의 첫 번째 음수:\n";
   findFirstNegIntWindowK(arr, n, k);
   return 0;
}

출력 결과

크기가 2인 각 윈도우의 첫 번째 음수:
-2 -1 -1 0 -6

정리

두 가지 접근법을 비교해 보면, 중첩 루프를 사용하는 브루트 포스 방식은 구현이 간단하지만 O(n*k)의 시간이 걸리는 반면, 덱을 활용한 슬라이딩 윈도우 방식은 각 요소를 최대 한 번씩만 처리하므로 O(n)의 선형 시간에 문제를 해결할 수 있습니다. 대용량 데이터를 다룰 때는 덱 기반 접근법이 훨씬 효율적입니다.