문제 설명
'L', 'R', 그리고 0부터 9까지의 숫자로 구성된 문자열 S가 주어진다고 가정해 봅시다. 왼쪽에서 오른쪽 순서로 0번부터 9번까지 번호가 붙은 객실 10개를 가진 호텔이 있다고 생각해 보겠습니다. 이 호텔에는 왼쪽과 오른쪽, 두 개의 출입구가 있습니다.
손님이 왼쪽 출입구로 도착하면 왼쪽 출입구에서 가장 가까운 빈 객실을 배정받고, 오른쪽 출입구로 도착하면 오른쪽 출입구에서 가장 가까운 빈 객실을 배정받습니다. 안타깝게도 객실 배정 목록을 잃어버렸지만, 모든 손님에 대해 어떤 출입구로 들어왔는지, 언제 몇 번 객실에서 퇴실했는지는 기억하고 있습니다. 처음에 호텔은 모두 비어 있었으며, 우리는 이 기록을 바탕으로 객실 배정 내역을 복원해야 합니다.
문자열 S에서 'L'은 손님이 왼쪽에서 들어왔음을, 'R'은 오른쪽에서 들어왔음을, 숫자 d는 d번 객실의 손님이 퇴실했음을 의미합니다. 최종 결과는 길이 10의 문자열로 반환하며, '0'은 빈 객실, '1'은 사용 중인 객실을 나타냅니다.
예시
입력이 S = "LLRL1RL1"라면 출력은 "1010000011"이 됩니다. 단계별로 살펴보면 다음과 같습니다.
- 초기 상태 – 모든 객실이 비어 있음 → 0000000000
- L – 손님이 왼쪽 출입구로 도착 → 1000000000
- L – 손님이 왼쪽 출입구로 도착 → 1100000000
- R – 손님이 오른쪽 출입구로 도착 → 1100000001
- L – 손님이 왼쪽 출입구로 도착 → 1110000001
- 1 – 1번 객실의 손님이 퇴실 → 1010000001
- R – 손님이 오른쪽 출입구로 도착 → 1010000011
- L – 손님이 왼쪽 출입구로 도착 → 1110000011
- 1 – 1번 객실의 손님이 퇴실 → 1010000011
풀이 접근 방식
이 문제는 다음 단계를 따라 해결할 수 있습니다.
n := 문자열 S의 길이
a := "0000000000"
i := 0부터 i < n일 때까지 반복(i는 1씩 증가):
만약 S[i]가 'L'이라면:
a에서 가장 왼쪽의 '0'을 '1'로 변경
그렇지 않고 S[i]가 'R'이라면:
a에서 가장 오른쪽의 '0'을 '1'로 변경
그 외의 경우(숫자인 경우):
a의 S[i]번째 자리를 '0'으로 변경
a 반환
C++ 구현 예시
아래 코드를 통해 더 잘 이해해 보겠습니다. 각 문자를 정확히 한 번씩만 처리하도록 조건문을 else if 구조로 작성한 점에 유의하세요.
#include <bits/stdc++.h>
using namespace std;
string solve(string S) {
int n = S.size();
string a = "0000000000";
for (int i = 0; i < n; i++) {
if (S[i] == 'L')
a[a.find('0')] = '1';
else if (S[i] == 'R')
a[a.rfind('0')] = '1';
else
a[S[i] - '0'] = '0';
}
return a;
}
int main() {
string S = "LLRL1RL1";
cout << solve(S) << endl;
}
코드 핵심 포인트
a.find('0'): 문자열 a에서 첫 번째 '0', 즉 가장 왼쪽의 빈 객실 위치를 찾습니다.a.rfind('0'): 문자열 a에서 마지막 '0', 즉 가장 오른쪽의 빈 객실 위치를 찾습니다.S[i] - '0': 문자형 숫자를 정수 인덱스로 변환해 해당 객실을 다시 빈 상태('0')로 만듭니다.
시간 복잡도는 문자열 길이를 n이라 할 때 각 문자마다 최대 10칸을 탐색하므로 O(n × 10), 즉 O(n)입니다.
입력
"LLRL1RL1"
출력
1010000011