파이썬에서 빈 좌석과 점유 좌석 사이의 최대 거리를 찾는 프로그램

<시간/>

좌석이라고 하는 0과 1만 있는 목록이 있다고 가정합니다. 여기서 Seat[i]는 좌석을 나타냅니다. 1이면 점유되고 그렇지 않으면 비어 있습니다. 자유석이 하나 이상 있고 점유석이 하나 이상 있으므로 자유석에서 가장 가까운 점유석까지의 최대 거리를 찾아야 합니다.

따라서 입력이 Seats =[1, 0, 1, 0, 0, 0, 1]과 같으면 출력은 2가 됩니다. 왜냐하면 우리는 Seats[4]를 차지할 수 있고 거리는 2입니다.

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

해상도 :=0
마지막 :=-1
n :=좌석 크기
범위 0에서 n - 1에 있는 i에 대해 수행
- Seat[i]가 1이면
  - res :=최대 res 및 (i if last <0 그렇지 않으면 floor of (i-last)/2)
  - 마지막 :=나는
res 및 (n-last-1)
의 최대값을 반환합니다.

예

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

def solve(seats):
   res, last, n = 0, -1, len(seats)
   for i in range(n):
      if seats[i]:
         res = max(res, i if last < 0 else (i - last) // 2)
         last = i
   return max(res, n - last - 1)

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

입력

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