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

1월 26일 오늘의 문제 

 

0과 1로 구성되는 배열과 k가 주어지고, 배열 값이 1일때 k 범위안에 또 다른 1이 있으면 False, 끝까지 탐색했을 때는 True

 

n^2으로 풀 수 있는 문제 

앞에서부터 가면서 1을 만나면, 앞/뒤로 k범위 안에 1이 있는지 확인

    def kLengthApart(self, nums: [int], k: int) -> bool:
        for i, num in enumerate(nums):
            # 현재 값이 1이면 내 위치에서 i-k, i+k 안에 1이 들어 있었는지 확인
            if num == 1:
                for j in range(i-k, i):
                    if j<0:continue
                    if nums[j] == 1:
                        return False

                for j in range(i+1, i+k+1):
                    if j>=len(nums):break
                    if nums[j] == 1:
                        return False

        return True

 

01/26/2021 08:15

Accepted

592 ms

16.8 MB

python3

 

좀 더 빠르게 풀 수 있는 방법이 있을까? 비트연산도 있다는데..이건 나중에 공부해보자

 

k를 이용하면 된다. 
즉, 1을 만나면 k범위 안에 1이 있는 지 판별한다는 것은 이전의 1과 다음 1 사이에 k만큼 0이 있으며 된다. 

만약 k가 2라면,  두번째 1을 만났을때 0의 갯수가 2개이다. 즉 k이므로 True가 된다.

1

0

0

1

0

    def kLengthApart(self, nums: [int], k: int) -> bool:
        # 1을 만나기전까지 0의 갯수를 세고, 1을 만나면 count와 k를 비교
        count = 0
        for num in nums:
            if num == 1:
                if count < k:
                    return False
                count = 0
            else:
                count += 1
        return True

01/26/2021 08:32

Accepted

540 ms

16.9 MB

python3