Python으로 배열에 연속된 세 개의 홀수가 있는지 확인하는 방법

배열 nums가 주어졌을 때, 이 배열 안에 연속된 세 개의 홀수가 존재하는지 확인하는 프로그램을 만들어 보겠습니다.

예를 들어 입력이 다음과 같다고 가정해 봅시다.

nums = [18, 15, 2, 19, 3, 11, 17, 25, 20]

이 경우 [3, 11, 17]처럼 연속된 세 개의 홀수가 존재하므로 출력 결과는 True가 됩니다.

문제 해결 접근 방법

이 문제는 배열을 한 번만 순회하면서 인접한 세 원소씩 검사하면 간단히 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

• 먼저 배열의 길이를 구합니다.
• 배열의 길이가 1 또는 2라면 세 개의 연속된 원소 자체가 존재할 수 없으므로 False를 반환합니다.
• 그렇지 않은 경우, 인덱스 i를 0부터 (배열 길이 - 3)까지 반복하면서 다음을 검사합니다.
  • nums[i], nums[i+1], nums[i+2]가 모두 홀수라면 True를 반환합니다.
• 끝까지 검사했는데도 조건을 만족하는 구간이 없다면 False를 반환합니다.

Python 구현 예제

위 로직을 Python 코드로 구현하면 다음과 같습니다.

def solve(nums):
    length = len(nums)
    if length == 1 or length == 2:
        return False
    else:
        for i in range(len(nums) - 2):
            if nums[i] % 2 != 0 and nums[i+1] % 2 != 0 and nums[i+2] % 2 != 0:
                return True
        return False

nums = [18, 15, 2, 19, 3, 11, 17, 25, 20]
print(solve(nums))

입력

[18, 15, 2, 19, 3, 11, 17, 25, 20]

출력

True

코드 설명 및 복잡도 분석

홀수 판별은 나머지 연산자 %를 사용하여 수행됩니다. 어떤 수를 2로 나눈 나머지가 0이 아니면 그 수는 홀수입니다. 반복문은 배열의 끝에서 두 번째 원소까지만 순회하므로, 마지막 두 원소와 비교할 때 인덱스 범위를 벗어나는 오류가 발생하지 않습니다.

이 알고리즘의 시간 복잡도는 배열을 한 번 순회하므로 O(n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 따라서 매우 효율적인 해결 방법이라고 할 수 있습니다.