0과 1로만 이루어진 리스트 seats가 있다고 가정해 보겠습니다. 여기서 seats[i]는 하나의 좌석을 나타내며, 값이 1이면 해당 좌석은 이미 점유된 상태이고, 0이면 비어 있는 상태입니다. 리스트에는 적어도 하나의 빈 좌석과 하나의 점유된 좌석이 존재할 때, 빈 좌석에서 가장 가까운 점유 좌석까지의 거리 중 최댓값을 구하는 것이 문제입니다.
예를 들어 입력이 seats = [1, 0, 1, 0, 0, 0, 1]이라면 출력은 2가 됩니다. 인덱스 4의 좌석에 앉으면 양쪽의 점유 좌석(인덱스 2와 6)까지의 거리가 각각 2이므로, 이 경우가 최대 거리가 되기 때문입니다.
문제 해결 접근 방법
이 문제는 리스트를 한 번만 순회하면서 선형 시간(O(n))에 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 마지막으로 확인한 점유 좌석의 위치를 변수
last에 저장합니다. - 새로운 점유 좌석을 만나면, 현재 위치와 이전 점유 좌석 사이의 거리를 계산합니다.
- 두 점유 좌석 사이의 빈 좌석이라면 거리는 두 위치 차이의 절반이 되고, 리스트 맨 앞의 빈 좌석이라면 현재 위치 자체가 거리가 됩니다.
알고리즘 단계
res := 0으로 초기화합니다.last := -1로 초기화합니다.n := len(seats)로 리스트의 크기를 저장합니다.- i를 0부터 n-1까지 반복하며:
seats[i]가 1이면:res를res와 (last가 음수이면i, 아니면(i - last) // 2) 중 더 큰 값으로 갱신합니다.last := i로 갱신합니다.
- 최종적으로
res와(n - last - 1)중 더 큰 값을 반환합니다. 이는 리스트 맨 뒤쪽 빈 좌석의 경우를 처리하기 위함입니다.
마지막 단계에서 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]
출력
2
시간 및 공간 복잡도
이 알고리즘은 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가적인 공간을 사용하지 않으므로 공간 복잡도는 O(1)입니다. 따라서 좌석 수가 많아져도 효율적으로 동작합니다.