문제 개요
동물들의 초기 상태를 나타내는 문자열 s가 주어졌다고 가정해 보겠습니다. 각 동물은 다음 세 가지 상태 중 하나를 가집니다.
L: 왼쪽으로 이동하는 동물
R: 오른쪽으로 이동하는 동물
@: 제자리에 정지해 있는 동물
한 방향으로 이동 중인 동물은 반대 방향에서 힘을 받지 않는 한 마주치는 다른 동물들을 끌고 가 함께 움직입니다. 하지만 반대 방향의 힘을 동시에 받게 되면 그 자리에 멈춰 서게 됩니다. 우리의 목표는 모든 동물이 멈췄을 때 각 동물의 최종 방향을 구하는 것입니다.
예를 들어 입력이 s = "@@L@R@@@@L"이라면 출력은 "LLL@RRRLLL"이 됩니다.
해결 접근 방법
이 문제는 너비 우선 탐색(BFS)과 유사한 레벨 기반 전파 방식으로 효율적으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
levels := 문자열 s와 같은 크기의 리스트를 만들고 모든 값을 -1로 초기화합니다.
q := 양방향 큐(deque)를 생성합니다.
idx를 0부터 s의 길이까지 순회하면서, s[idx]가 "R" 또는 "L"이면 (idx, 0, s[idx])를 q의 끝에 추가합니다.
l := 문자열 s의 각 문자를 담은 새 리스트를 만듭니다.
q가 빌 때까지 다음을 반복합니다.
(idx, new_level, dir) := q의 왼쪽 요소를 꺼냅니다.
만약 levels[idx]가 -1이라면(아직 힘이 도달하지 않은 칸), levels[idx] := new_level로 설정하고 l[idx] := dir로 방향을 기록합니다. 이후 dir이 "R"이고 idx + 1 < len(l)이면 (idx + 1, new_level + 1, dir)을 q에 추가하고, dir이 "L"이고 idx - 1 >= 0이면 (idx - 1, new_level + 1, dir)을 q에 추가합니다.
그렇지 않고 levels[idx]가 new_level과 같다면(같은 레벨에서 힘이 도달한 경우), l[idx]가 dir과 다를 때 l[idx] := "@"로 설정하여 두 힘이 상쇄되었음을 표시합니다.
마지막으로 l의 요소들을 이어 붙인 문자열을 반환합니다.
동작 원리
핵심 아이디어는 힘이 퍼져 나가는 과정을 레벨 단위로 추적하는 것입니다. 처음에 'L' 또는 'R'인 위치를 모두 큐에 넣고, BFS처럼 인접 칸으로 힘을 전파합니다. 어떤 칸에 가장 먼저 도달한 힘이 그 칸의 방향을 결정하고, 같은 레벨에서 서로 다른 방향의 힘이 동시에 도달하면 두 힘이 균형을 이루어 해당 동물은 '@'로 표시되어 멈추게 됩니다.
예시 구현
아래 파이썬 코드를 통해 더 잘 이해해 보겠습니다.
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