문제 소개
길이가 n인 문자열 S가 있다고 가정해 봅시다. 이 문자열은 서로 인접하게 늘어선 n개의 상자를 나타내며, 각 위치의 문자는 다음과 같은 의미를 가집니다.
- R — 해당 위치의 상자가 오른쪽으로 밀려나고 있음
- L — 해당 위치의 상자가 왼쪽으로 밀려나고 있음
- . — 빈 공간
초기 배치에서 시작해 매 시간 단위마다 오른쪽으로 밀리는 상자는 바로 옆 상자를 오른쪽으로 밀어낼 수 있으며, 왼쪽 방향도 동일하게 적용됩니다. 목표는 더 이상 어떤 움직임도 일어나지 않는 시점의 모든 상자의 최종 위치를 구하는 것입니다.
예를 들어 입력이 R..R...L.라면 최종 결과는 RRRRR.LL.이 됩니다.
해결 전략: 두 번의 선형 순회
이 문제는 각 칸에 작용하는 오른쪽 힘과 왼쪽 힘을 따로 계산해 합산하면 깔끔하게 풀립니다. 절차는 다음과 같습니다.
- 왼쪽 → 오른쪽 순회: 'R'을 만나면 오른쪽 힘을 최대치(N)로 설정하고, 'L'을 만나면 0으로 초기화합니다. 빈 공간에서는 힘이 1씩 감소하되 0 미만으로 내려가지 않습니다. 각 위치에서 이 힘을 movement 배열에 더합니다.
- 오른쪽 → 왼쪽 순회: 반대 방향으로 같은 규칙을 적용해 왼쪽 힘을 계산하고, movement 배열에서 차감합니다.
- 결과 변환: 최종 배열의 값이 양수면 'R', 음수면 'L', 0이면 '.'으로 바꿔 문자열을 만듭니다.
구현 코드
아래 파이썬 코드로 위 전략을 그대로 구현할 수 있습니다.
def get_final_pos(string):
N = len(string)
movement = [0] * N
m = 0
# 1단계: 왼쪽 → 오른쪽 순회 (오른쪽 힘 누적)
for i in range(N):
if string[i] == 'R':
m = N
elif string[i] == 'L':
m = 0
else:
m = max(m - 1, 0)
movement[i] += m
m = 0
# 2단계: 오른쪽 → 왼쪽 순회 (왼쪽 힘 차감)
for i in range(N - 1, -1, -1):
if string[i] == 'L':
m = N
elif string[i] == 'R':
m = 0
else:
m = max(m - 1, 0)
movement[i] -= m
# 3단계: 부호에 따라 최종 문자 결정
return "".join('.' if m == 0 else 'R' if m > 0 else 'L' for m in movement)
print(get_final_pos('R..R...L.'))실행 결과
입력:
'R..R...L.'출력:
RRRRR.LL.예제 동작 과정 분석
입력 R..R...L.(길이 9)을 단계별로 추적해 보겠습니다.
1단계(왼쪽 → 오른쪽): 인덱스 0의 'R'이 힘 9를 발생시키고, 빈 칸을 지날 때마다 1씩 줄어듭니다. 인덱스 3의 'R'이 다시 9로 초기화하고, 인덱스 7의 'L'이 힘을 0으로 만듭니다. 그 결과 movement 배열은 [9, 8, 7, 9, 8, 7, 6, 0, 0]이 됩니다.
2단계(오른쪽 → 왼쪽): 인덱스 7의 'L'이 왼쪽 힘 9를 발생시켜 인덱스 6, 5, 4에는 각각 8, 7, 6이 기록되고, 인덱스 3의 'R'이 힘을 0으로 초기화합니다. 이 힘들을 차감하면 최종 배열은 [9, 8, 7, 9, 2, 0, -2, -9, 0]이 됩니다.
3단계(변환): 양수는 'R', 음수는 'L', 0은 '.'으로 바꾸면 RRRRR.LL.이 완성됩니다. 특히 인덱스 5처럼 양쪽 힘이 정확히 상쇄되는 지점은 평형 상태, 즉 빈 공간('.')으로 남게 됩니다.
복잡도 분석
시간 복잡도는 문자열을 두 번 순회하므로 O(n), 공간 복잡도는 movement 배열 때문에 O(n)입니다. 상자 수와 무관하게 일정한 성능을 보장하는 효율적인 접근법입니다.