0과 1로만 구성된 배열 nums와 정수 k가 주어졌을 때, 배열에 있는 모든 1이 서로 최소 k칸 이상 떨어져 있는지 확인하는 문제입니다. 조건을 만족하지 않으면 false를 반환해야 합니다.
예를 들어 입력이 nums = [1,0,0,0,1,0,0,1], k = 2라면 출력은 true가 됩니다. 각각의 1이 서로 최소 2칸 이상 떨어져 있기 때문입니다.
문제 해결 접근 방식
이 문제는 배열을 한 번만 순회하면서 직전에 등장한 1의 위치를 기억하는 그리디 방식으로 해결할 수 있습니다. 단계별 접근 방법은 다음과 같습니다.
- 변수
last를 -1로 초기화합니다. 아직 1을 만나지 못했다는 의미입니다. - i를 0부터 nums의 크기까지 순회하며 다음을 반복합니다.
nums[i]가 1이라면:last가 -1이거나(첫 번째 1인 경우),(i - last - 1) >= k라면 두 1 사이의 간격이 충분하므로last := i로 갱신합니다.- 그렇지 않다면 간격이 부족하므로 즉시 false를 반환합니다.
- 순회가 끝나면 모든 조건을 통과한 것이므로 true를 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool kLengthApart(vector<int>& nums, int k) {
int last = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == 1) {
if (last == -1 || (i - last - 1) >= k)
last = i;
else
return false;
}
}
return true;
}
};
main(){
Solution ob;
vector<int> v = {1,0,0,0,1,0,0,1};
cout << (ob.kLengthApart(v, 2));
}입력
{1,0,0,0,1,0,0,1}출력
1
출력값 1은 true를 의미하며, 배열 내 모든 1이 최소 2칸 이상 떨어져 있음을 나타냅니다.
복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)이고, 추가적인 공간 없이 단일 변수만 사용하므로 공간 복잡도는 O(1)입니다. 따라서 매우 효율적인 선형 시간 해결책입니다.