1. 문제 소개

1437. Check If All 1's Are at Least Length K Places Away

2. 나의 풀이

처음 보자마자 nums를 순회하여 0을 만날 때마다 distance를 올렸고 1을 만날 때 d가 k보다 작은 경우 True/False를 체크했다.
시간복잡도는 $O(n)$이다.

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        d = 0                       # 연속된 0의 개수를 세는 거리 카운터
        First1 = True               # 첫 번째 1을 아직 본 적 있는지 여부
        for i, num in enumerate(nums):  # nums 전체를 순회하며 인덱스와 값을 확인
            if num == 0:
                d += 1              # 0이면 거리 증가 (1 사이의 간격 누적)
            elif num == 1 and First1:
                First1 = False      # 첫 번째 1을 만나면 기준점 설정
                d = 0               # 거리 카운터 초기화
            else:
                if d < k:           # 두 번째 이후의 1에서 거리 조건 검사
                    return False    # 간격이 k 미만이면 조건 위반 → False
                d = 0               # 조건 충족 시 거리 초기화 후 다음으로 진행
        return True                 # 모든 검사 통과 시 True

3. 다른 풀이

방식은 같지만 조금 더 빠른 풀이도 존재한다.

class Solution:
    def kLengthApart(self, nums: List[int], k: int) -> bool:
        if k == 0:                      # k가 0이면 1 사이 간격 요구가 없으므로 항상 True
            return True
        
        prev = None                     # 이전에 등장한 '1'의 인덱스를 저장할 변수 (처음엔 없음)

        for i, num in enumerate(nums):  # 배열을 순회하면서 인덱스 i와 값 num을 확인
            if num == 1:                # 현재 위치에 1이 등장했다면
                if prev is not None and i - prev <= k:
                    # 직전에 본 1의 위치(prev)와 현재 1의 위치(i) 사이 거리가 k 이하라면
                    # 두 1 사이 간격이 조건보다 좁으므로 False 반환
                    return False
                prev = i                # 문제 없으면 현재 위치를 새로운 prev로 갱신
        
        return True                     # 모든 1들 사이 간격이 조건을 만족하면 True

4. 결론

쉬운 문제여서 잘 풀 수 있었다.