파이썬에서 모두가 앉을 수 있는지 확인하는 프로그램

숫자 n이 있고 좌석을 찾는 n명의 사람들이 있다고 가정하고 1은 이미 점유된 좌석을 나타내고 0은 빈 좌석을 나타내는 비트 목록도 있습니다. 두 사람이 나란히 앉을 수 없기 때문에 n명이 모두 자리를 잡을 수 있는지 확인해야 합니다.

따라서 입력이 n =2 석 =[1, 0, 0, 0, 1, 0, 0]과 같으면 출력은 인덱스 2와 6에 앉을 수 있으므로 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 좌석의 시작 부분에 0을 삽입하고 좌석의 끝에 [0, 1]을 삽입
• res :=0, 간격 :=0
• 좌석에 있는 각 i에 대해 다음을 수행합니다.
  • i가 0과 같으면
    • 갭 :=갭 + 1
  • 그렇지 않으면 갭> 0일 때
    • res :=res + floor of (gap - 1)/2
    • 갭:=0
• res>=n일 때 true를 반환하고 그렇지 않으면 false

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def solve(n, seats):
   seats = [0] + seats + [0, 1]
   res = 0
   gap = 0
   for i in seats:
      if i == 0:
         gap += 1
      elif gap > 0:
         res += (gap - 1) // 2
         gap = 0
   return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))

입력

2, [1, 0, 0, 0, 1, 0, 0]

출력

True