'L', 'R' 및 0에서 9까지의 숫자가 포함된 문자열 S가 있다고 가정합니다. 왼쪽에서 오른쪽으로 0에서 9까지 번호가 매겨진 10개의 객실이 있는 호텔이 있다고 가정합니다. 호텔에는 두 개의 입구가 있습니다. 하나는 왼쪽에 있고 다른 하나는 오른쪽에 있습니다. 고객이 왼쪽 입구를 통해 호텔에 도착하면 왼쪽 입구에서 가장 가까운 빈 방을 얻습니다. 마찬가지로 고객이 오른쪽 입구를 통해 호텔에 도착하면 오른쪽 입구에서 가장 가까운 빈 방을 얻습니다. 그러나 우리는 방 배정 목록을 잃어 버렸습니다. 그러나 우리는 모든 고객을 기억합니다. 고객이 언제 도착했는지, 어느 입구에서, 호텔을 떠날 때. 처음에는 호텔이 비어 있었습니다. 메모리에서 방 배정 목록을 복구해야 합니다. S에서 'L'은 왼쪽에서 온 사람을 의미하고, 'R'이면 오른쪽에서 온 사람을 의미하며, 숫자 d는 고객이 d방을 나가는 것을 나타냅니다. 방 상태를 반환해야 합니다. 길이가 10이고 0인 문자열은 공간이 비어 있음을 의미하고 그렇지 않으면 점유됩니다.
따라서 입력이 S ="LLRL1RL1"과 같으면 출력은 "1010000011"이 됩니다.
우선 모든 방이 비어 있습니다. 상태 0000000000.
L - 고객은 왼쪽 입구를 통해 호텔에 도착합니다. 상태 1000000000.
L - 왼쪽 입구의 고객. 상태 1100000000.
R - 오른쪽 입구의 고객. 상태 1100000001.
L - 왼쪽 입구의 고객. 상태 1110000001.
1 - 1번 방의 고객이 나갑니다. 상태 1010000001.
R - 오른쪽 입구의 고객. 상태 1010000011.
L - 왼쪽 입구의 고객. 상태 1110000011.
1 - 1번 방의 고객이 나갑니다. 상태 1010000011.
단계
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
n := size of S a := "0000000000" for initialize i := 0, when i < n, update (increase i by 1), do: if S[i] is same as 'L', then: set left most 0 in a to 1 if S[i] is same as 'R', then: set right most 0 in a to 1 Otherwise set S[i]th place in a to 0 return a
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
#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';
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;
} 입력
"LLRL1RL1"
출력
1010000011