문제 이해하기
숫자 n이 주어지고, n명의 사람이 각각 앉을 자리를 찾고 있다고 가정해 봅시다. 또한 0과 1로 이루어진 좌석 리스트가 있는데, 여기서 1은 이미 사용 중인 좌석, 0은 비어 있는 좌석을 의미합니다.
단, 두 사람이 서로 바로 옆자리에 앉는 것은 허용되지 않습니다. 따라서 우리가 확인해야 할 것은 n명의 사람이 모두 이 조건을 만족하는 자리를 찾을 수 있는지 여부입니다.
예를 들어, n = 2이고 seats = [1, 0, 0, 0, 1, 0, 0]이라면 결과는 True입니다. 두 사람은 각각 인덱스 2와 인덱스 6에 서로 인접하지 않게 앉을 수 있기 때문입니다.
해결 접근 방법
이 문제는 연속된 빈 좌석(0)의 개수, 즉 '갭(gap)'을 세는 방식으로 효율적으로 해결할 수 있습니다. 양쪽이 차 있는 상태에서 길이가 g인 연속된 빈 좌석 구간에는 최대 (g - 1) // 2명이 인접하지 않고 앉을 수 있습니다.
배열의 시작과 끝 경계도 동일한 로직으로 처리하기 위해, 좌석 리스트의 맨 앞에 0을 추가하고 맨 뒤에는 [0, 1]을 추가합니다. 이렇게 하면 행의 양 끝에 있는 빈 좌석도 내부 구간과 같은 방식으로 계산됩니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 좌석 리스트의 맨 앞에 0을 삽입하고, 맨 끝에 [0, 1]을 삽입합니다.
- 결과 카운터 res와 갭 카운터 gap을 0으로 초기화합니다.
- 좌석 리스트의 각 요소 i에 대해 다음을 수행합니다.
- i가 0이면 gap을 1 증가시킵니다.
- i가 1이고 gap이 0보다 크면, res에 (gap - 1) // 2를 더한 후 gap을 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동작 원리 살펴보기
위 예제에서 좌석 배열은 경계 처리 후 [0, 1, 0, 0, 0, 1, 0, 0, 0, 1]로 변환됩니다. 첫 번째 1 앞에는 길이 1의 갭이 있고, 두 개의 1 사이에는 길이 3의 갭이 있으며, 마지막 1 앞에도 길이 3의 갭이 존재합니다.
이를 계산하면 (1-1)//2 = 0, (3-1)//2 = 1, (3-1)//2 = 1이므로 총 res = 2가 됩니다. n = 2이므로 res >= n 조건을 만족하여 True가 반환됩니다.
이 알고리즘은 좌석 리스트를 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 복잡도 역시 O(n)입니다. 좌석 수에 비례해 선형적으로 처리되므로 매우 효율적인 그리디 기반 해법이라 할 수 있습니다.