Python에서 리스트의 모든 1이 연속으로 나타나는지 확인하는 방법

숫자로 이루어진 리스트 nums가 주어졌을 때, 이 리스트에는 값이 1인 원소가 최소 하나 이상 포함되어 있습니다. 우리가 확인해야 할 것은 모든 1이 서로 인접하게(연속적으로) 나타나는지 여부입니다.

예를 들어 입력이 nums = [8, 2, 1, 1, 1, 3, 5]라면, 세 개의 1이 모두 붙어 있으므로 출력은 True가 됩니다. 반면 [1, 2, 1]처럼 1 사이에 다른 숫자가 끼어 있다면 False를 반환해야 합니다.

해결 접근 방식

이 문제는 상태 플래그 하나만으로 간단히 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 상태를 저장할 변수 visited를 0으로 초기화합니다. (0: 아직 1을 만나지 않음, 1: 1이 등장 중인 구간, 2: 1이 끝난 후)

• 리스트의 각 원소 x를 순회하며 다음을 검사합니다.

  • x가 1인 경우: 이미 visited가 2라면, 즉 1이 한 번 끊긴 적이 있다면 False를 반환합니다. 그렇지 않으면 visited를 1로 설정합니다.

  • x가 1이 아니면서 visited가 0이 아닌 경우: 1의 연속 구간이 방금 끝났음을 의미하므로 visited를 2로 설정합니다.

• 순회가 끝날 때까지 위반 사항이 없다면 True를 반환합니다.

구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

def solve(nums):
   visited = 0
   for x in nums:
      if x == 1:
         if visited == 2:
            return False
         visited = 1
      elif visited:
         visited = 2
   return True

nums = [8, 2, 1, 1, 1, 3, 5]
print(solve(nums))

입력

[8, 2, 1, 1, 1, 3, 5]

출력

True

복잡도 분석

이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 추가로 사용하는 공간은 상태 변수 하나뿐이므로 공간 복잡도는 O(1)로 매우 효율적입니다.