개념
크기가 N인 배열 arr1[]과 키 값 X, 그리고 세그먼트 크기 K가 주어졌을 때, 키 X가 배열 내 크기 K를 가진 모든 세그먼트에 존재하는지 판별하는 것이 이 문제의 목표입니다.
입력 예제 1
arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 }
X = 4
K = 3출력
Yes
위 배열에는 크기 K(=3)인 겹치지 않는 세그먼트가 총 4개 존재합니다: {4, 6, 3}, {5, 10, 4}, {2, 8, 4}, {12, 13, 4}. 네 개의 세그먼트 모두에 4가 포함되어 있으므로 결과는 Yes입니다.
입력 예제 2
arr1[] = { 22, 24, 57, 66, 35, 55, 77, 33, 24, 46, 22, 24, 26 }
X = 24
K = 5출력
Yes
입력 예제 3
arr1[] = { 6, 9, 8, 13, 15, 4, 10 }
X = 9
K = 2출력
No
접근 방법
해결 아이디어는 매우 직관적입니다. 배열을 처음부터 순회하면서 크기 K인 각 세그먼트(윈도우)를 차례대로 검사하고, 해당 윈도우 안에 X가 존재하는지 확인하면 됩니다.
다만 한 가지 주의할 점이 있습니다. 배열의 길이 N이 K로 나누어 떨어지지 않는 경우, 마지막 세그먼트의 크기는 K보다 작을 수 있습니다. 따라서 남은 원소들로 구성된 마지막 부분 배열도 별도로 처리해 주어야 정확한 결과를 얻을 수 있습니다.
구현 예제
다음은 위 접근 방식을 C++로 구현한 코드입니다.
// 배열의 모든 세그먼트에 검색 키 x가 존재하는지 확인하는 C++ 코드
#include <bits/stdc++.h>
using namespace std;
bool findxinkindowSize1(int arr1[], int X, int K, int N){
int i;
// 인덱스 i부터 시작하는 세그먼트에서 X 탐색
for (i = 0; i < N; i = i + K) {
int j;
for (j = 0; j < K; j++)
if (arr1[i + j] == X)
break;
// 반복문이 break 없이 끝났다면 해당 세그먼트에 X 없음
if (j == K)
return false;
}
// N이 K의 배수인 경우
if (i == N)
return true;
// N이 K의 배수가 아니라면 마지막 세그먼트 검사
int j;
for (j = i - K; j < N; j++)
if (arr1[j] == X)
break;
if (j == N)
return false;
return true;
}
// 메인 드라이버
int main(){
int arr1[] = { 4, 6, 3, 5, 10, 4, 2, 8, 4, 12, 13, 4 };
int X = 4, K = 3;
int N = sizeof(arr1) / sizeof(arr1[0]);
if (findxinkindowSize1(arr1, X, K, N))
cout << "Yes" << endl;
else
cout << "No" << endl;
return 0;
}
출력 결과
Yes
코드 설명 및 시간 복잡도
바깥쪽 반복문은 인덱스를 K씩 증가시키며 각 세그먼트의 시작 위치를 가리키고, 안쪽 반복문은 해당 세그먼트 내에서 키 X를 찾습니다. 만약 어떤 세그먼트에서 X를 발견하지 못하면 즉시 false를 반환하여 불필요한 연산을 줄입니다.
모든 세그먼트를 통과한 후에는 N이 K의 배수인지 확인합니다. 배수라면 모든 검사가 완료된 것이므로 true를 반환하고, 그렇지 않다면 마지막 잘린 세그먼트에 대해 추가 검사를 수행합니다.
각 원소는 최대 두 번(세그먼트 검사 시 한 번, 경계 처리 시 한 번) 방문될 수 있으므로 전체 시간 복잡도는 O(N)이며, 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다.