문제 링크

내 코드

못 풀었다..

구체적인 아이디어가 없는..

class Solution {
public:
    bool canChange(string start, string target) {
        // ___L => L___ (_, L 포함)
        // R___ => ___R (R, _ 포함)
        int startL{}, endL{}; // [startL, endL)
        int startR{}, endR{};// [startR, endR)
        for(int s{}, e{static_cast<int>(start.target())}; s < e ; ++ s) {
            if(start[s] == '_') {
                if(startR != endR) {
                    // 기존에 쌓은 구간 확인
                }
            }
        }
    }
};

Solution

Approach 1: Brute Force (Memory Limit Exceeded)

• Memory Limit Exceeded
• Complexity
  • Let $n$ be the size of the start and target strings.
  • Time Complexity: $O(n^2)$
  • Space Complexity: $O(n^2)$

class Solution {
public:
    bool canChange(string start, string target) {
        // To keep track of visited states to avoid cycles
        unordered_set<string> visitedStates;
        // Queue for current state
        queue<string> stateQueue;
        // Start with the initial state
        stateQueue.push(start);

        while (!stateQueue.empty()) {
            string currentState = stateQueue.front();
            stateQueue.pop();

            // If we reach the target state, return true
            if (currentState == target) return true;

            for (int position = 1; position < currentState.size(); position++) {
                // Try moving 'L' to the left
                if (currentState[position] == 'L' &&
                    currentState[position - 1] == '_') {
                    swap(currentState[position], currentState[position - 1]);
                    if (visitedStates.find(currentState) ==
                        visitedStates.end()) {
                        // Add the new state to the queue
                        stateQueue.push(currentState);
                        // Mark the new state as visited
                        visitedStates.insert(currentState);
                    }
                    // Restore the state
                    swap(currentState[position], currentState[position - 1]);
                }
                // Try moving 'R' to the right
                if (currentState[position - 1] == 'R' &&
                    currentState[position] == '_') {
                    swap(currentState[position], currentState[position - 1]);
                    if (visitedStates.find(currentState) ==
                        visitedStates.end()) {
                        // Add the new state to the queue
                        stateQueue.push(currentState);
                        // Mark the new state as visited
                        visitedStates.insert(currentState);
                    }
                    // Restore the state
                    swap(currentState[position], currentState[position - 1]);
                }
            }
        }

        // If no valid transformation sequence is found, return false
        return false;
    }
};

Approach 2: Using Queue

• 43ms, 37.83MB
• Complexity
  • Let $n$ be the size of the start and target strings.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool canChange(string start, string target) {
        // Queue to store characters and indices from both strings
        queue<pair<char, int>> startQueue, targetQueue;

        // Record non-underscore characters and their indices
        for (int i = 0; i < start.size(); i++) {
            if (start[i] != '_') {
                startQueue.push({start[i], i});
            }
            if (target[i] != '_') {
                targetQueue.push({target[i], i});
            }
        }

        // If number of pieces don't match, return false
        if (startQueue.size() != targetQueue.size()) return false;

        // Compare each piece's type and position
        while (!startQueue.empty()) {
            auto [startChar, startIndex] = startQueue.front();
            startQueue.pop();
            auto [targetChar, targetIndex] = targetQueue.front();
            targetQueue.pop();

            // Check character match and movement rules
            if (startChar != targetChar ||
                (startChar == 'L' && startIndex < targetIndex) ||
                (startChar == 'R' && startIndex > targetIndex))
                return false;
        }

        return true;
    }
};

GPT

아래는 LeetCode 문제 “Move Pieces to Obtain a String”를 한국어로 자세히 설명한 내용입니다.

문제 개요:
문자열 s를 시작점으로 하여 문자열 t를 만들고자 합니다. 두 문자열은 같은 문자 집합(L, R, _)을 갖고 있으며, 주어진 규칙에 따라 문자를 이동시킬 수 있습니다. 이동 규칙은 다음과 같습니다.

• ‘R’ 문자는 오른쪽으로만 이동할 수 있음: 즉, 오른쪽에 빈 칸(’_‘)이 있을 때만 ‘R’을 오른쪽 칸으로 옮길 수 있습니다.
• ‘L’ 문자는 왼쪽으로만 이동할 수 있음: 즉, 왼쪽에 빈 칸(’_‘)이 있을 때만 ‘L’을 왼쪽 칸으로 옮길 수 있습니다.

이때, s에서 시작해 위 규칙에 따라 문자를 움직여서 t를 만들 수 있는지 판단하는 문제입니다.

핵심 아이디어:

• ‘R’은 절대로 왼쪽으로 갈 수 없고, ‘L’은 절대로 오른쪽으로 갈 수 없습니다.
• 이 말은 결국, s에서의 ‘R’의 상대적인 순서와 위치 조건이 t에서도 충족되어야 하고, 마찬가지로 ‘L’도 그렇습니다.
• 구체적으로:
  • ‘R’ 문자는 처음 위치보다 왼쪽에 있을 수 없습니다. (오른쪽 이동만 가능하므로, 최종적으로 ‘R’은 s에서의 위치보다 t에서의 위치가 같거나 더 오른쪽에 있어야 함)
  • ‘L’ 문자는 처음 위치보다 오른쪽에 있을 수 없습니다. (왼쪽 이동만 가능하므로, 최종적으로 ‘L’은 s에서의 위치보다 t에서의 위치가 같거나 더 왼쪽에 있어야 함)

또한, ‘L’과 ‘R’의 상대적 순서는 바뀔 수 없습니다. 예를 들어, s에서 첫 번째 ‘R’이 두 번째 ‘R’보다 왼쪽에 있었다면, t에서도 여전히 첫 번째 ‘R’은 두 번째 ‘R’보다 왼쪽에 있어야 합니다. ‘L’에 대해서도 마찬가지이며, ‘R’와 ‘L’ 사이의 상대적 순서 또한 규칙적으로 유지됩니다.
즉, s에서 등장하는 ‘R’의 순서와 t에서 등장하는 ‘R’의 순서가 같고, s에서 ‘L’의 순서와 t에서의 ‘L’의 순서도 같아야 합니다. 순서가 달라진다면 ‘R’와 ‘L’이 서로를 건너뛰어야 하는 상황이 발생하는데, 이는 주어진 이동 규칙으로 불가능합니다.

접근법 (큐/리스트 사용):

1. 문자 빈도와 구성이 일치하는지 확인:
   s와 t가 ‘L’, ‘R’, ’_’ 문자를 동일한 개수로 가지고 있지 않다면, 변환은 불가능합니다.

2. ‘L’과 ‘R’의 인덱스 추출:
   s 문자열을 순회하여 ‘R’ 문자가 등장하는 인덱스를 모두 s_R 리스트(또는 큐)에 저장하고, ‘L’ 문자가 등장하는 인덱스를 s_L 리스트에 저장합니다.
   t 문자열에 대해서도 동일하게 t_R, t_L을 구합니다.

   예를 들어,
   s = “R_L” 라면, s_R = [1], s_L = [3]
   t = “_RL” 라면, t_R = [2], t_L = [2]

3. ‘R’ 인덱스 검증:
   s와 t에서 ‘R’의 인덱스 리스트 길이가 같고, 등장 순서가 같아야 합니다.
   그리고 각 i에 대해 s_R[i] ≤ t_R[i] 여야 합니다.
   왜냐하면 ‘R’은 오른쪽으로만 이동할 수 있으므로, 최종 위치 t_R[i]는 처음 위치 s_R[i]보다 왼쪽에 있을 수 없습니다.
   만약 t_R[i] < s_R[i]인 경우, ‘R’을 왼쪽으로 옮기는 것은 불가능하므로 실패합니다.

4. ‘L’ 인덱스 검증:
   s와 t에서 ‘L’의 인덱스 리스트 역시 길이와 순서가 같아야 합니다.
   그리고 각 i에 대해 s_L[i] ≥ t_L[i] 여야 합니다.
   왜냐하면 ‘L’은 왼쪽으로만 이동할 수 있으므로, 최종 위치 t_L[i]가 시작 위치 s_L[i]보다 오른쪽에 있을 수 없습니다.
   만약 t_L[i] > s_L[i]인 경우, ‘L’을 오른쪽으로 옮기는 것은 불가능하므로 실패합니다.

5. 모든 조건 충족 시 성공:
   위의 모든 검사를 통과하면 s에서 t로의 변환이 가능합니다.

이 접근법의 이유:

• 문자열 내에서 문자들을 실제로 하나하나 옮기는 복잡한 시뮬레이션을 하지 않고, 인덱스 조건만으로 가능 여부를 판단할 수 있습니다.
• ‘R’은 왼쪽으로 못 가고, ‘L’은 오른쪽으로 못 간다는 제약이 결국 인덱스 비교로 귀결됩니다.
• ‘R’와 ‘L’의 상대적 순서를 검사함으로써 불가능한 재배열을 사전에 차단합니다.

예시:
s = “R_L”
t = “_RL”

• s_R = [1], s_L = [3]
• t_R = [2], t_L = [2]

‘R’ 체크: s_R[0] = 1, t_R[0] = 2 → s_R[0] ≤ t_R[0] (1 ≤ 2) 만족
’L’ 체크: s_L[0] = 3, t_L[0] = 2 → s_L[0] ≥ t_L[0] (3 ≥ 2) 만족

모두 조건을 만족하므로 s를 t로 변환하는 것은 가능합니다.

정리하자면, 이 방법(Approach 2 using Queue)은 문자 각각의 인덱스를 따로 추출하여, ‘R’는 오른쪽 이동 조건(s_R[i] ≤ t_R[i])을, ‘L’은 왼쪽 이동 조건(s_L[i] ≥ t_L[i])을 만족하는지만 확인함으로써 문제를 단순화시키고 변환 가능 여부를 판단하는 방식입니다.

Approach 3: Two pointer

• 4ms, 21.7MB
• Complexity
  • Let $n$ be the size of the start and target strings.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool canChange(string start, string target) {
        int startLength = start.size();
        // Pointer for start string and target string
        int startIndex = 0, targetIndex = 0;

        while (startIndex < startLength || targetIndex < startLength) {
            // Skip underscores in start
            while (startIndex < startLength && start[startIndex] == '_') {
                startIndex++;
            }
            // Skip underscores in target
            while (targetIndex < startLength && target[targetIndex] == '_') {
                targetIndex++;
            }
            // If one string is exhausted, both should be exhausted
            if (startIndex == startLength || targetIndex == startLength) {
                return startIndex == startLength && targetIndex == startLength;
            }

            // Check if the pieces match and follow movement rules
            if (start[startIndex] != target[targetIndex] ||
                (start[startIndex] == 'L' && startIndex < targetIndex) ||
                (start[startIndex] == 'R' && startIndex > targetIndex))
                return false;

            startIndex++;
            targetIndex++;
        }

        // If all conditions are satisfied, return true
        return true;
    }
};

GPT

아래는 LeetCode 문제 “Move Pieces to Obtain a String”의 에디토리얼 중 접근 방법 3 (Two Pointer Approach)을 한국어로 자세히 설명한 내용입니다.

접근 방법 3 (Two Pointer):

핵심 아이디어:
이 접근법은 투 포인터(Two Pointer) 기법을 이용하여 문자열 s와 t를 동시에 순회하며, 각 문자를 적절히 매칭하는지 검사하는 방식입니다. 앞서 언급한 원리를 기억하면, ‘R’은 오른쪽으로만 이동 가능하고, ‘L’은 왼쪽으로만 이동 가능하며, 따라서 s에서 나온 ‘R’이 t에서 대응하는 ‘R’보다 오른쪽에 있을 수 없고, s에서 나온 ‘L’이 t에서 대응하는 ‘L’보다 왼쪽에 있을 수 없습니다.

구체적인 방법은 다음과 같습니다:

1. 전처리:
   s와 t가 동일한 문자 구성(동일한 수의 ‘R’, ‘L’, ’_‘)을 가지고 있는지 먼저 확인합니다. 만약 문자 구성이 다르다면 바로 false를 반환합니다.

2. 두 포인터 사용:
   인덱스 i, j를 두 문자열 s와 t에 각각 두고, 두 문자열을 동시에 순회합니다.

   • i: 문자열 s를 순회하는 포인터
   • j: 문자열 t를 순회하는 포인터

   여기서 ‘_’(빈칸)는 실제로 문자를 옮기는 데 있어서 중요한 장애물이 아니라, 단지 이동 가능 공간을 나타냅니다. 우리가 궁극적으로 맞춰야 하는 것은 s에 있는 ‘L’들과 ‘R’들이 t에서 같은 순서, 그리고 가능한 위치 관계를 만족하는가입니다.

3. 포인터 이동 로직: 문자열 s와 t에서 ‘L’ 또는 ‘R’ 문자를 만날 때까지 각각 i와 j를 이동합니다. 빈칸('')은 건너뛰어도 됩니다. 즉, s[i]가 ''라면 i를 증가시켜 다음 문자를 탐색하고, t[j]가 ’_‘라면 j를 증가시켜 다음 문자를 탐색합니다.

   • s[i]와 t[j] 모두 알파벳 ‘L’ 또는 ‘R’을 찾은 경우, 두 문자가 서로 같은지 확인합니다.

     • 만약 s[i] != t[j] 라면, 순서를 맞출 수 없으므로 바로 false를 반환합니다.

   • s[i]와 t[j]가 같은 문자라면, 이 문자가 ‘R’인지, ‘L’인지에 따라 위치 관계를 확인해야 합니다.

     • 만약 ‘R’이라면, s에서의 위치 i는 t에서의 위치 j보다 항상 작거나 같아야 합니다. (s_R[i] ≤ t_R[j])
       왜냐하면 ‘R’은 오른쪽으로만 이동 가능하므로, 최종적으로 t에서 ‘R’이 있는 인덱스 j는 시작점 s의 인덱스 i보다 왼쪽에 있을 수 없습니다.
       만약 i > j라면, s의 ‘R’은 t에서 요구하는 위치보다 왼쪽에 있어야 하는데, ‘R’은 왼쪽으로 이동할 수 없으므로 불가능합니다.

     • 만약 ‘L’이라면, s에서의 위치 i는 t에서의 위치 j보다 항상 크거나 같아야 합니다. (s_L[i] ≥ t_L[j])
       왜냐하면 ‘L’은 왼쪽으로만 이동 가능하므로, 최종적으로 t에서 ‘L’이 있는 인덱스 j는 시작점 s의 인덱스 i보다 오른쪽에 있을 수 없습니다.
       만약 i < j라면, s의 ‘L’은 t에서 요구하는 위치보다 오른쪽에 있어야 하는데, ‘L’은 오른쪽으로 이동할 수 없으므로 이 역시 불가능합니다.

   이 조건들을 만족하지 않는 순간 false를 반환합니다.

4. 모두 만족할 경우:
   s와 t에서 더 이상 비교할 ‘L’이나 ‘R’ 문자가 없고, 모든 위치 제약을 만족했다면 true를 반환합니다.

정리:

• 투 포인터 기법으로 s와 t를 동시에 순회합니다.
• 빈칸(’_‘)은 무시하고, ‘L’이나 ‘R’ 문자를 찾을 때까지 각각 진행합니다.
• ‘L’, ‘R’을 각각 짝지을 때, s의 인덱스와 t의 인덱스 관계를 검사하여 이동 가능 여부를 판별합니다.
• 모든 문자 짝에 대해 조건이 만족되면 true, 중간에 하나라도 불가능한 조건이 나오면 false입니다.

예시를 통한 이해:

예를 들어, s = “R_L”와 t = “_RL”:

• s: '', ‘R’, '', ‘L’, ’_’
• t: '', '', ‘R’, ‘L’, ’_’

두 포인터 i, j를 각각 s와 t 처음에 둡니다.

• s에서 i를 오른쪽으로 이동: s[0] = ’_’ → i=1
  s[1] = ‘R’, 이제 ‘R’을 찾음.
• t에서 j를 오른쪽으로 이동: t[0] = '', t[1] = '' → j=2
  t[2] = ‘R’, 이제 ‘R’을 찾음.

이제 s[i]=R, t[j]=R이므로 같은 문자입니다. ‘R’인 경우, s의 인덱스(i=1) ≤ t의 인덱스(j=2)이어야 합니다. 여기서는 1 ≤ 2이므로 만족.

다음 ‘L’을 찾기 위해 s와 t에서 각각 i와 j를 진행:

• s에서 i를 증가: i=2에서 ’_’, i=3에서 ‘L’ 발견.
• t에서 j를 증가: j=3에서 ‘L’ 발견.

이제 s[i]=L, t[j]=L이므로 같은 문자입니다. ‘L’인 경우, s의 인덱스(i=3) ≥ t의 인덱스(j=3)이어야 합니다. 여기서는 3 ≥ 3이므로 만족.

마지막까지 조건을 위배하지 않고 모두 만족했으므로 결과는 true입니다.

이 접근법은 별도의 자료구조 없이 O(n) 시간에 가능하며, 두 문자열을 한 번에 순회하면서 조건을 점검하기 때문에 직관적이고 효율적입니다.