문제 소개
컨벤션 센터에 입장하려는 프로그래머가 총 n명 있다고 가정해 보겠습니다. 또한 숫자로 이루어진 리스트가 하나 주어지는데, 여기서 1은 이미 자리에 앉아 있는 프로그래머를, 0은 빈자리를 의미합니다. 이때 중요한 조건은 두 프로그래머가 서로 바로 옆에 나란히 앉을 수 없다는 것입니다. 우리가 확인해야 할 것은 n명의 프로그래머가 모두 컨벤션에 입장할 수 있는지 여부입니다.
예를 들어 입력이 n = 2이고 convention = [0, 0, 1, 0, 0, 0, 1]이라면, 양옆이 모두 비어 있는 자리에 프로그래머를 차례로 배치할 수 있으므로 출력 결과는 True가 됩니다.
해결 접근 방법
이 문제는 리스트를 한 번 순회하면서 빈자리의 양옆 상태를 검사하는 그리디 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 인덱스 0부터 conv의 길이까지 반복합니다.
- 각 위치 i에 대해 왼쪽 인덱스 a와 오른쪽 인덱스 b를 계산합니다. 배열 경계를 벗어나지 않도록 처리하는 것이 핵심입니다.
- a := i-1이 0보다 작으면 0, 그렇지 않으면 i-1
- b := i+1이 conv의 길이보다 크거나 같으면 len(conv)-1, 그렇지 않으면 i+1
- conv[i], conv[a], conv[b]가 모두 0이라면 해당 자리에 프로그래머를 앉힐 수 있습니다.
- conv[i] := 1로 변경
- n := n - 1로 감소
- 반복이 끝난 후 n <= 0이면 True를 반환하고, 그렇지 않으면 False를 반환합니다.
구현 예제 코드
class Solution:
def solve(self, n, conv):
for i in range(len(conv)):
a = 0 if i - 1 < 0 else i - 1
b = len(conv) - 1 if i + 1 >= len(conv) else i + 1
if conv[i] == 0 and conv[a] == 0 and conv[b] == 0:
conv[i] = 1
n -= 1
return n <= 0
ob = Solution()
n = 2
convention = [0, 0, 1, 0, 0, 0, 1]
print(ob.solve(n, convention))
입력
2, [0, 0, 1, 0, 0, 0, 1]
출력
True
코드 동작 원리
리스트 [0, 0, 1, 0, 0, 0, 1]에서 첫 번째 인덱스 0은 왼쪽 경계이지만 자신과 오른쪽 칸이 모두 비어 있으므로 프로그래머를 배치할 수 있습니다. 이후 인덱스 4 역시 양옆(인덱스 3과 5)이 모두 0이므로 배치가 가능합니다. 이렇게 두 명을 배치하면 n이 0이 되어 최종적으로 True가 반환됩니다.
경계 처리 부분(i-1이 음수가 되거나 i+1이 배열 길이를 넘는 경우)을 클램핑 방식으로 처리하기 때문에, 배열의 맨 앞이나 맨 뒤 자리도 안전하게 검사할 수 있습니다.
시간 및 공간 복잡도
이 알고리즘은 리스트를 단 한 번 순회하므로 시간 복잡도는 O(m)입니다(m은 리스트의 길이). 배치 과정에서 추가적인 자료 구조를 사용하지 않으므로 공간 복잡도는 O(1)로 매우 효율적입니다.