문제 정의
문자열 s와 숫자 k가 주어집니다. 문자열의 각 문자는 점('.') 또는 'x'이며, 점은 비어 있는 공간을, 'x'는 사람이 서 있는 자리를 의미합니다. 목표는 임의의 위치에 섰을 때 가장 가까운 사람과의 거리가 k 이상이 되도록 설 수 있는지 판별하는 것입니다. 이때 인접한 인덱스 사이의 거리는 1로 계산합니다.
예를 들어 s = "x...x..", k = 2가 입력이라면 결과는 True입니다. 인덱스 2 또는 인덱스 6에 서면 가장 가까운 사람과의 거리가 정확히 2가 되어 조건을 만족하기 때문입니다.
해결 알고리즘
핵심 아이디어는 세 가지 경우를 차례로 검사하는 것입니다.
- 시작 부분 확인: 문자열에 'x'가 아예 없다면 어디든 자유롭게 설 수 있으므로 True입니다. 또한 첫 번째 'x'의 위치가 k보다 크거나 같다면 맨 앞(인덱스 0)에 설 수 있으므로 역시 True입니다.
- 두 사람 사이 확인: 연속된 두 'x' 사이의 빈 칸 개수가 2k − 1개 이상이면 그 사이 한가운데에 서서 양쪽 모두 k 이상 떨어질 수 있습니다. 따라서 dist_min을 2*k−1로 설정하고, 인접한 'x'들 사이의 간격을 순차적으로 검사합니다.
- 끝 부분 확인: 마지막 'x' 뒤에 남은 빈 칸이 k개 이상이면 문자열 끝에 설 수 있으므로 True, 그렇지 않으면 False입니다.
구현 예제
class Solution:
def solve(self, s, k):
pos = s.find("x")
if pos == -1 or pos >= k:
return True
last_x = pos
dist_min = 2 * k - 1
while True:
next_x = s.find("x", last_x + 1)
if next_x != -1:
if next_x - last_x - 1 >= dist_min:
return True
last_x = next_x
else:
if len(s) - last_x - 1 >= k:
return True
return False
ob = Solution()
print(ob.solve("x...x..", 2))
입력
"x...x..", 2
출력
True
동작 원리 살펴보기
입력 "x...x.."에서 첫 번째 'x'는 인덱스 0에 있습니다. pos(0)가 k(2)보다 작으므로 즉시 True를 반환하지 않고 루프에 진입하며, dist_min은 2×2−1 = 3이 됩니다. 다음 'x'는 인덱스 4에 있고, 두 'x' 사이의 빈 칸 수는 4 − 0 − 1 = 3으로 dist_min 이상입니다. 따라서 인덱스 2에 서면 왼쪽 사람과 오른쪽 사람 모두 거리 2를 유지할 수 있으므로 True가 반환됩니다.
이 알고리즘은 문자열을 한 번만 순회하므로 시간 복잡도는 O(n)이며, 추가 메모리 사용량은 O(1)로 매우 효율적입니다.