문자열 s와 숫자 k가 있다고 가정합니다. 이제 문자열의 각 문자는 점('.') 또는 'x'입니다. 여기서 점은 빈 공간을 나타내고 'x'는 사람을 나타냅니다. 우리와 가장 가까운 사람 사이의 거리가 최소 k 이상 되도록 서 있는 위치를 선택할 수 있는지 확인해야 합니다. (여기서 각 인접 인덱스 간의 거리는 1입니다).
따라서 입력이 s ="x...x..", k =2와 같으면 출력은 s[2] 또는 s[6]에 있을 수 있으므로 True가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- pos :=s에서 x의 위치, 존재하지 않으면 pos는 -1이 됩니다.
- pos가 -1 또는 pos>=k와 같으면
- 참 반환
- last_x :=위치
- dist_min :=2*k-1
- 무한 루프, do
- next_x :=인덱스 last_x+1에서 끝까지 s의 x 위치(x가 없으면 -1이 됨)
- next_x가 -1과 같지 않으면
- next_x-last_x-1>=dist_min이면
- 참 반환
- last_x :=next_x
- next_x-last_x-1>=dist_min이면
- 그렇지 않으면
- 크기가 s -last_x-1>=k이면
- 거짓을 반환
- 크기가 s -last_x-1>=k이면
- null 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
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
return None
ob = Solution() print(ob.solve("x...x..", 2)) 입력
"x...x..", 2
출력
True