You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:
- The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
- The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.
Return true if it is possible to obtain the string target by moving the pieces of the string start any number of times. Otherwise, return false.
Example 1:
Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "L______RR".
Since it is possible to get the string target from start, we return true.
Example 2:
Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.
Example 3:
Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.
Constraints:
- n == start.length == target.length
- 1 <= n <= 105
- start and target consist of the characters 'L', 'R', and '_'.
은근 까다로운 문제다.
그래도 for문 돌리면 풀 수 있을 거 같은 생각이 드니까 함 해보자
1. Python
아나 또 적절히 코딩했더니, Time complexity에 걸렸다. 답은 나온다..
class Solution:
def canChange(self, start: str, target: str) -> bool:
if (start.count('L') != target.count('L')) or (start.count('R') != target.count('R')):
return False
n = len(start)
for i in range(n):
if start[i] == target[i]:
continue
# Need move
temp = target[i]
if (start[i] == 'L')or(start[i] == '_' and temp == 'R')or(start[i] == 'R' and temp =='L'):
return False
if start[i] == '_' and temp == 'L' :
for j in range(i+1,n):
if start[j] == '_': continue
if start[j] == 'R': return False
if start[j] == 'L':
start = start[:i] + start[j] + start[i+1:j] + start[i] + start[j+1:]
break
if start[i] == 'R' and temp == '_' :
for j in range(i+1,n):
if start[j] == '_':
start = start[:i] + start[j] + start[i+1:j] + start[i] + start[j+1:]
break
if start[j] == 'R': continue
if start[j] == 'L': return False
return True
문제는 Python 내에서 String을 저렇게 Slice치고 쪼개고 붙치는게 시간소모가 크다.
그래서 아래와 같이 index를 이용해 깔롱지게 만들 수가 있다.
만약에 문제가 BOOL 형태의 output이 아니고, 중간중간 String의 변형과정을 다 보여줘야 하는 것이면 나처럼 풀어야겠지만, target string으로 바꿀 수 있는지 가부여부만 체크하는 함수면 아래와 같이 푸는게 효율적이다.
enumerate( => index, char 동시에 저장)을 잘 활용하고, zip이라는 놈을 이용하면 for문 돌릴 때 더 편하다.
class Solution:
def canChange(self, start: str, target: str) -> bool:
if start.replace('_',"") != target.replace('_',""):return False
start_lst = [(idx,char) for idx,char in enumerate(start) if char != '_']
target_lst = [(idx,char) for idx,char in enumerate(target) if char != '_']
temp = zip(start_lst,target_lst)
for (idx_s,char_s),(idx_t,char_t) in temp:
if char_s != char_t : return False
if char_s == 'L' and (idx_s < idx_t) : return False
if char_s == 'R' and (idx_s > idx_t) : return False
return True
zip 사용 예시
target1 = "LLL___RRR"
target2 = "___LRLRLR"
test1 = [(char,i) for i,char in enumerate(target1)]
test2 = [(char,i) for i,char in enumerate(target2)]
print(test1)
print(test2)
test3=zip(test1,test2)
for a in test3:
print(a)
"""
[('L', 0), ('L', 1), ('L', 2), ('_', 3), ('_', 4), ('_', 5), ('R', 6), ('R', 7), ('R', 8)]
[('_', 0), ('_', 1), ('_', 2), ('L', 3), ('R', 4), ('L', 5), ('R', 6), ('L', 7), ('R', 8)]
(('L', 0), ('_', 0))
(('L', 1), ('_', 1))
(('L', 2), ('_', 2))
(('_', 3), ('L', 3))
(('_', 4), ('R', 4))
(('_', 5), ('L', 5))
(('R', 6), ('R', 6))
(('R', 7), ('L', 7))
(('R', 8), ('R', 8))
"""
string을 다루기엔 좀 짜치긴하지만,,
그래도 혹시 모르니 C, C++도 함 풀어보자
2. C / C++
#define MAX_LEN 100000
bool canChange(char* start, char* target) {
int sL[MAX_LEN];
int sR[MAX_LEN];
int tL[MAX_LEN];
int tR[MAX_LEN];
int n = strlen(start);
char new_start[MAX_LEN];
char* new_target = (char*)malloc(MAX_LEN*sizeof(char));
// Step 1: Remove '_' and check stripped strings
int k = 0;
for(int i=0;i<n;i++){
if(start[i] != '_') new_start[k++] = start[i];
}
new_start[k] = '\0';
k = 0;
for(int i=0;i<n;i++){
if(target[i] != '_') new_target[k++] = target[i];
}
new_target[k] = '\0';
if(strcmp(new_start,new_target) != 0) return false;
// Step 2: Extract positions of 'L' and 'R'
int a=0, b=0, c=0, d=0;
for(int i=0; i<n; i++){
if(start[i]=='L') sL[a++] = i;
else if(start[i]=='R') sR[b++] = i;
if(target[i]=='L') tL[c++] = i;
else if(target[i]=='R') tR[d++] = i;
}
// Step 3: Compare positions of 'L' and 'R'
for(int i=0;i<a;i++){
if(sL[i] < tL[i]) return false;
}
for(int i=0;i<b;i++){
if(sR[i] > tR[i]) return false;
}
return true;
}
C++
class Solution {
public:
bool canChange(string start, string target) {
int n = start.size();
// Step 1: Remove '_' and check stripped strings
string startStripped, targetStripped;
for (char c : start) {
if (c != '_') startStripped += c;
}
for (char c : target) {
if (c != '_') targetStripped += c;
}
if (startStripped != targetStripped) return false;
// Step 2: Extract positions of 'L' and 'R'
vector<int> startL, startR, targetL, targetR;
for (int i = 0; i < n; i++) {
if (start[i] == 'L') startL.push_back(i);
if (start[i] == 'R') startR.push_back(i);
if (target[i] == 'L') targetL.push_back(i);
if (target[i] == 'R') targetR.push_back(i);
}
// Step 3: Compare positions of 'L' and 'R'
for (int i = 0; i < startL.size(); i++) {
if (startL[i] < targetL[i]) return false; // 'L' can only move left
}
for (int i = 0; i < startR.size(); i++) {
if (startR[i] > targetR[i]) return false; // 'R' can only move right
}
return true;
}
};
C++에선 C에 비해 array Initialize가 편하고, index 처리가 편하다..!