leetcode medium : Maximize Distance to Closest Person

https://leetcode.com/problems/maximize-distance-to-closest-person/description/

풀기 전

Exam Room 축소판같다.

이 문제 먼저 풀고 Exam Room 푸는게 맞는 순서였을듯..

빈공간이 끝에있을경우인 엣지케이스도 동일하게 적용된다.

이번 문제는 가장 큰 빈공간 하나만 찾으면 되므로 원스캔으로 풀 수 있을 것이다.

빈공간이 시작되는 지점을 저장해놨다가 빈공간이 끝날때마다 distance to closest person을 갱신해주면 된다.

코드 설명

class Solution:
    def maxDistIfSeat(self, begin, end, n):
        if begin > end:
            return -1
        if begin == 0:
            return end + 1
        if end == n - 1:
            return n - begin
        return (end - begin) // 2 + 1

    def maxDistToClosest(self, seats: List[int]) -> int:
        begin = 0
        maxdist = 0

        for i in range(len(seats) + 1):
            if i == len(seats) or seats[i]:
                maxdist = max(maxdist, self.maxDistIfSeat(begin, i-1, len(seats)))
                begin = i + 1

        return maxdist

maxDistIfSeat는 begin부터 end까지의 빈공간에 앉을경우 max distance to closest person이다.

for문으로 O(N)스캔을 한다. len(seats) 뒤에 +1을 추가한 이유는 리스트가 빈공간으로 끝나는 경우는 if seat[i] 조건에 걸리지 않아서 maxdist계산이 되지 않기 때문이다. 그래서 i == len(seats)라는 조건을 임의로 추가했다.

분석

시간복잡도 O(N)

공간복잡도 O(1)

솔루션 학습

maxDistIfSeat함수를 간단하게 없앨 수 있어보인다.

def maxDistToClosest(self, seats: List[int]) -> int:
       
        prev, max_len = 0, 0
        
        for cur, seat in enumerate(seats):
            if seat:
                if seats[prev]:
                    max_len = max(max_len, (cur - prev) // 2)
                else:
                    max_len = max(max_len, (cur - prev))
                prev = cur
                
        if seats[prev]: 
            max_len = max(max_len, len(seats) - 1 - prev) 
                
        return max_len