[Codeforces] awoo's Favorite Problem with Two Pointers💥

분명 처음에 접할 때는 단순한 BFS 문제로 생각해서 쉽다고 여겼으나, 역시나 또 다시 시간 초과를 맞닥뜨렸다.

아무래도 주어진 규칙에 내포된 패턴을 파악해야 하는데, 그렇지 못하고 계속 규칙만을 활용한 무식한 방법을 써서 그런 것 같다.

 

그래도 시간 초과를 방지하기 위해 만든 장치

1. 중복 탐색을 막기 위한 set

2. 목표로 하는 t 문자열과 다른 알파벳 구간부터 교체

(즉 ab에서 ba로, bc에서 cb로 바꿀 수 있어도 목표로하는 문자열과 동일하면 교체 X)

 

위 장치를 도입해도 시간 초과가 발생하였다.

아무리 생각해도 내 뇌 용량을 초과하는 문제인 것 같아서 대회 후 댓글을 결국 열어 보았다.

 

교체 패턴을 살펴보면, ab → ba, bc → cb 식으로만 가능하다.

이를 통해 아래와 같은 발견을 할 수 있다.

 

# 1. s와 t는 각각 a, b, c 개수가 동일해야한다

# 2. c는 왼쪽으로만 갈 수 있다.

# 3. a는 오른쪽으로만 갈 수 있다.

 

# 2:

c를 왼쪽으로(인덱스 i에서 인덱스 j로) 옮기기 위해서는 범위 [j, i - 1]는 모두 b들로 구성되어 있어야 한다.

만약 불가능하면 우리는 strring s에서 t로 바꾸지 못한다.

 

# 3: 

a를 오른쪽으로(인덱스 j에서 인덱스 i로) 옮기기 위해서는 범위 [j + 1, i]는 모두 c들로 구성되어 있어야 한다.

만약 불가능하면 우리는 strring s에서 t로 바꾸지 못한다.

 

There seem to be more solutions to C. I'll explain mine.

First, we need to make a few observations:

1. both strings s and t should have equal amounts of 'a', 'b', and 'c'
2. 'c' cannot be moved towards right in string s (So, each 'c' in s should be present towards the right of its counterpart in string t)
3. 'a' cannot be moved towards left in string s (So, each 'a' in s should be present towards the left of its counterpart in string t) by doing the given operations.

Let's start with the observation#2:

To move a 'c' towards the left from index i to j(j < i), the range [j, i-1] should have all 'b's. Try moving each 'c' in s to its correct position in t. If we cannot move a 'c', we cannot convert s to t.

Now, all 'c's should be in their correct positions(if possible)

Similarly, with the observation#3:

To move a 'a' towards the right from index j to i(j < i), the range [j+1, i] should have all 'c's. Try moving each 'a' in s to its correct position in t. If we cannot move a 'a', we cannot convert s to t.

Now all 'a's should be in their correct positions(if possible)

Since all 'a's and 'c's are in their correct positions, now we just need to check if all b's are there in their correct positions and determine the answer.

Implementation:

To check if a range contains all b's and make point updates while moving a character from one index i to j(the move is a direct swap of s[i] and s[j] and not actual swaps between adjacent characters to reach the destination), we can use Segment Tree with range query and point updates.

 

위에서 언급된 특징들을 활용해 다음과 같은 알고리즘을 구성할 수 있다. 만약 손으로 그려보면 나도 스스로 충분히 알아낼 수 있었을텐데..

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int q, len;
    string s, t;
    cin >> q;
    while(q--) {
        cin >> len;
        vector<pair<char, int>> vec_s;
        vector<pair<char, int>> vec_t;
        cin >> s >> t;
        for(int i = 0;i < len;i++) {
            if(s[i] != 'b') vec_s.push_back({s[i], i});
            if(t[i] != 'b') vec_t.push_back({t[i], i});
        }
        
        if(vec_s.size() != vec_t.size()) {
            cout << "NO" << '\n';
            continue;
        }
        int size = vec_s.size();
        bool result = true;
        for(int i = 0;i < size;i++) {
            if(vec_s[i].first == 'c' && vec_t[i].first == 'c') {
                if(vec_s[i].second < vec_t[i].second) {
                    result = false;
                    break;
                }
            }
            else if(vec_s[i].first == 'a' && vec_t[i].first == 'a') {
                if(vec_s[i].second > vec_t[i].second) {
                    result = false;
                    break;
                }
            }
            else {
                result = false;
                break;
            }
        }
        
        if(result) {
            cout << "YES" << '\n';
        }
        else {
            cout << "NO" << '\n';
        }
    }
}

 

참고

https://codeforces.com/contest/1697/submission/160336788

Submission #160336788 - Codeforces

유사한 문제

https://leetcode.com/problems/swap-adjacent-in-lr-string/

Swap Adjacent in LR String - LeetCode