일부 동물의 초기 조건을 나타내는 문자열 s가 있다고 가정합니다. 각 동물은 세 가지 값 중 하나를 취할 수 있습니다. L은 동물이 왼쪽으로 이동했음을 나타냅니다. R은 동물이 오른쪽으로 이동했음을 나타냅니다. @는 동물이 가만히 서 있음을 나타냅니다. 동물이 반대 방향에서 힘을 받지 않는 한 한 방향으로 움직이는 동물은 다른 동물을 픽업합니다. 그러면 가만히 있을 것입니다. 동물이 움직임을 멈출 때 각 동물의 방향을 찾아야 합니다.
따라서 입력이 s ="@@L@R@@@@L"과 같으면 출력은 "LLL@RRRLLL"이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
수준 :=s와 동일한 크기 목록 및 -1로 채우기
-
q :=이중 종료 큐
-
idx가 0에서 s 크기의 범위에 있는 경우 다음을 수행하십시오.
-
s[idx]가 "R"과 같거나 s[idx]가 "L"과 같으면
-
q의 끝에 (idx, 0, s[idx]) 삽입
-
-
-
l :=s의 새 문자 목록
-
q가 비어 있지 않은 동안 수행
-
(idx, new_level, dir) :=q의 왼쪽 요소, q에서 삭제
-
수준[idx]이 -1과 같으면
-
수준[idx] :=new_level
-
l[idx] :=디렉토리
-
dir이 "R"이고 idx + 1
-
q의 끝에 (idx + 1, new_level + 1, dir) 삽입
-
-
그렇지 않으면 dir이 "L" 및 idx - 1>=0과 같을 때
-
q의 끝에 (idx - 1, new_level + 1, dir) 삽입
-
-
-
그렇지 않으면 수준[idx]이 new_level과 같을 때
-
l[idx]가 dir과 같지 않으면
-
l[idx] :="@"
-
-
-
-
l
의 요소를 결합하여 문자열을 반환합니다.
예
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
from collections import deque class Solution: def solve(self, s): levels = [-1 for i in s] q = deque() for idx in range(len(s)): if s[idx] == "R" or s[idx] == "L": q.append((idx, 0, s[idx])) l = list(s) while q: idx, new_level, dir = q.popleft() if levels[idx] == -1: levels[idx] = new_level l[idx] = dir if dir == "R" and idx + 1 < len(l): q.append((idx + 1, new_level + 1, dir)) elif dir == "L" and idx - 1 >= 0: q.append((idx - 1, new_level + 1, dir)) elif levels[idx] == new_level: if l[idx] != dir: l[idx] = "@" return "".join(l) ob = Solution() s = "@@L@R@@@@L" print(ob.solve(s))
입력
"@@L@R@@@@L"
출력
LLL@RRRLLL