[2024] day 184. Leetcode 1550. Three Consecutive Odds

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 7월 1일 (월)
Leetcode daily problem

1550. Three Consecutive Odds

https://leetcode.com/problems/three-consecutive-odds/?envType=daily-question&envId=2024-07-01

Problem

Solution

Brute Force

일단 처음에 접근한 방식은, 주어진 배열을 한 번 순회하면서 짝수는 0으로 홀수는 1로 변경한다.
그리고 이진으로 구성되어 있는 배열을 한 번 더 순회하면서
현재의 인덱스에서 3칸의 합이 3인, 즉 연속된 홀수가 있는지 체킹하고 있으면 바로 True를 반환, 순환할 때까지 없으면 False를 반환하도록 접근했다.

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        
        for i in range(len(arr)):
            if arr[i]%2==0:
                arr[i]=0
            else:
                arr[i]=1
                
        for i in range(len(arr)):
            if sum(arr[i:i+3])==3:
                return True
            
        return False

여기서는 주어진 배열을 탐색하고, 조건을 찾는 과정에서 배열의 원소만큼의 시간이 필요해서 전체 시간복잡도는 O(n)이고, 주어진 배열의 원소를 1,0으로 변환하기 때문에 추가적인 공간을 필요로하지 않아 전체 공간복잡도는 O(1)이다.

사실 근데 굳이 배열을 바이너리로 변환하지 않고
그냥 홀수의 연속 개수를 세면서 풀어도 될 일이다.

Code

class Solution:
    def threeConsecutiveOdds(self, arr: List[int]) -> bool:
        odd_cnt = 0
        for num in arr:
            if num%2==1:
                odd_cnt +=1
            else:
                odd_cnt = 0
            
            if odd_cnt ==3:
                return True
            
        return False

Complexicity

시간 복잡도

주어진 배열을 한 번 순회하면서, 홀수 이면 cnt를 업데이트 하고, 3에 도달하면 True를 반환하는데, 배열을 한번은 순회해야 하므로 시간복잡도는 O(n)이다.

공간 복잡도

상수 변수만 업데이트하므로 공간복잡도는 O(1) 이다.