R, B, 그리고 점(.) 세 가지 문자로 이루어진 문자열이 있다고 가정해 보겠습니다. 여기서 R은 현재 위치를, B는 막혀 있어 지나갈 수 없는 위치를, 점(.)은 비어 있는 위치를 의미합니다. 한 번의 이동으로 현재 위치에서 인접한 칸으로 움직일 수 있으며, 단 이동하려는 칸이 유효한(비어 있는) 곳이어야 합니다. 이때 가장 왼쪽 끝 또는 가장 오른쪽 끝 위치에 도달할 수 있는지 확인하는 것이 문제입니다.
예를 들어 입력이 s = "...........R.....BBBB....."와 같다면 출력은 True가 됩니다. R의 왼쪽 구간에는 장애물(B)이 하나도 없기 때문에, R이 가장 왼쪽 끝까지 자유롭게 이동할 수 있기 때문입니다.
문제 해결 접근 방식
이 문제는 생각보다 훨씬 간단하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
r_pos:= 문자열 s에서 'R'이 위치한 인덱스- 문자열 처음부터
r_pos - 1까지 구간에 'B'가 존재하지 않거나,r_pos부터 문자열 끝까지 구간에 'B'가 존재하지 않으면 True를 반환
즉, R을 기준으로 왼쪽 구간과 오른쪽 구간 중 어느 한쪽이라도 장애물이 없다면 해당 방향 끝까지 도달할 수 있다는 뜻입니다. 파이썬의 슬라이싱과 find() 메서드를 활용하면 이 조건을 한 줄로 깔끔하게 표현할 수 있습니다.
구현 예시
class Solution:
def solve(self, s):
r_pos = s.find('R')
return not 'B' in s[:r_pos] or not 'B' in s[r_pos:]
ob = Solution()
s = "...........R.....BBBB....."
print(ob.solve(s))
위 코드에서 s.find('R')은 문자열 내 R의 인덱스를 찾아주고, 슬라이싱 s[:r_pos]는 R의 왼쪽 구간, s[r_pos:]는 R을 포함한 오른쪽 구간을 나타냅니다. 각 구간에 'B'가 없는지 검사한 뒤 OR 연산으로 결과를 반환합니다.
입력
"...........R.....BBBB....."
출력
True
이 알고리즘은 문자열을 최대 두 번 순회하므로 시간 복잡도는 O(n)이며, 추가 공간 없이 제자리에서 처리되므로 공간 복잡도는 O(1)입니다. 문자열 길이가 매우 길어도 효율적으로 동작합니다.