[백준][C++] 9935 문자열폭발

대표적인 스택 활용 문제이다.

두시간을 왜 틀렸는지도 모른채 끙끙 앓았다.

결국 대회 테스트 케이스까지 가져다가 일일히 대입해서 반례를 찾기는 했는데,

결과값이 워낙 길다보니 텍스트 비교 사이트를 활용해가며 고민한 결과 문제점을 결국 알아냈다..

 

내가 떠올린 풀이법의 큰 틀은 다음과 같다.

 

1. 폭탄문자열의 각 문자와 그 문자의 인덱스를 맵으로 저장한다.

2. 주어진 문자열에서 한문자씩 반복하여 체크한다.

 

3-1. 그 문자가 폭탄문자열에 속해있지 않으면 정답 큐에 해당 문자를 넣는다.

3-2. 그 문자가 폭탄문자열에 속해있다면 그 문자의 인덱스를 가져온다.

 

4-1. 가져온 인덱스가 0이면 묻지도 따지지도 않고 count 스택에 넣는다.

4-2. 가져온 인덱스가 스택 상단의 인덱스보다 1크다면 스택 상단의 인덱스를 빼서

현재 인덱스로 교체한다.

(스택 최상단 인덱스의 값을 1 키운다)

 

5. 만약 스택 최상단의 인덱스 값이 폭탄문자열길이보다 1작다면

(모든 카운트가 다 찬경우)

스택 최상단의 인덱스 값을 빼내고

정답문자열에서 폭탄 문자열 길이만큼 문자를 뺀다.

---

나는 계속 2%에서 틀렸었다.

질문게시판에도 2%에서 틀린 사람들의 이야기가 꽤 있어서 읽어봤지만 크게 해결에 도움되는 내용은 없었다.

그래서 대회 테스트 케이스를 갖고 반례를 찾아 반례를 분석하기 시작했다.

 

내가 걸린 반례는 너무 길어서 다 담을 수 없지만

사용한 폭탄문자열은 다음과 같다.

quR1NQCTOncjroBElw3sAHZvftm2ShXVz

 

분석한 결과 지우면 안되는 문자열 2개를 지우는 것이 문제점이었다.

첫번째 문자열은

9uR1NQCTOncjroBElw3sAHZvftm2ShXVz

 

두번째 문자열은

Elw3sAHZvftm2ShXlw3sAHZvftm2ShXVz

이것이다.

 

이걸봐도 처음엔 왜 폭탄문자열이랑 다른걸 지우나 싶어서 이유를 모른채

디버그 모드를 활용하여 문자열을 지우는 순간에 break point를 걸고 변수값을 체크해보았다.

지우는 순간은 모두 폭탄 카운트를 max까지 채우고, 지우는 순간 마지막 문자열은 모두 z였다.

그렇다면 지우는 순간을 자체를 완전 엉뚱하게 짚어서 지운건 아니라는 말이다.

지우면 안되는 순간인데 지우는 순간과 비슷해서 구분을 못하고 있다는 뜻이다.

 

이점에서 착안해서 첫번째 문자열과 폭탄문자열을 비교해보았다.

첫글자만 다르다!

여기에서 바로 원인이 떠올랐다.

바로 묻지도 따지지도 않고 0번째 인덱스 문자는 카운트에 추가했던 것이다.

그렇게 0번 인덱스 문자를 추가해둔 상황에서 다른 문자들이 쭉 쌓여있다가

갑자기 1번째 인덱스부터 끝까지 제대로 들어온다면?

스택에서 0을 꺼낼 수 있으니 마지막 문자열까지 입력을 다 받은 순간

차례대로 지워나갈 것이다.

 

하지만 0번째 문자는 묻지도 따지지도 않고 카운트 스택에 추가해두는 것은 맞다.

따라서 중간에 폭탄문자열에 없는 문자가 들어오면 스택을 클리어해버리도록 했다.

중간에 폭탄문자열에 없는 문자가 들어온다면 어떤 수를 써도 문자열 폭발은 일어나지 않는다.

 

다음으로 두번째 문자열을 폭탄문자열과 비교해보았다.

아까와 비슷한 상황이다.

역시 원인을 떠올리기는 어렵지 않았다.

만약 0번부터 k번까지 문자열이 제대로 들어왔다고 해보자.

 

중간에 폭탄문자열에 없는 문자가 들어오면 아까 수정한 로직에 의해

스택은 클리어가 될 것이다.

 

하지만 폭탄문자열에 있지만 순서가 틀린 문자가 들어온다면?

저 녹색 문자를 자세히보면 모두 폭탄문자열에 있는 문자들이다.

 

그렇게 중간에 이 문자들이 쌓였다가 나중에 k+1번째 문자부터 마지막까지 제대로 들어온다면

이 로직에서는 폭탄문자열로 취급하고 지울 것이다.

 

따라서 0번째 인덱스도 아니고, 스택의 마지막 인덱스보다 1큰 인덱스가 아닌경우

그냥 스택을 비워버리도록 했다.

이 경우에도 아까와 마찬가지로 무슨 수를 써도 폭발은 일어나지 않기 때문이다.

 

따라서 수정된 로직은 다음과 같다.

 

1. 폭탄문자열의 각 문자와 그 문자의 인덱스를 맵으로 저장한다.

2. 주어진 문자열에서 한문자씩 반복하여 체크한다.

 

3-1. 그 문자가 폭탄문자열에 속해있지 않으면 정답 큐에 해당 문자를 넣는다.

+ 기존 count 스택을 초기화한다.

3-2. 그 문자가 폭탄문자열에 속해있다면 그 문자의 인덱스를 가져온다.

 

4-1. 가져온 인덱스가 0이면 묻지도 따지지도 않고 count 스택에 넣는다.

4-2. 가져온 인덱스가 스택 상단의 인덱스보다 1크다면 스택 상단의 인덱스를 빼서

현재 인덱스로 교체한다.

(스택 최상단 인덱스의 값을 1 키운다)

4-3 이외의 경우 count 스택을 초기화한다.

 

5. 만약 스택 최상단의 인덱스 값이 폭탄문자열길이보다 1작다면

(모든 카운트가 다 찬경우)

스택 최상단의 인덱스 값을 빼내고

정답문자열에서 폭탄 문자열 길이만큼 문자를 뺀다.

 

 

제출한 코드는 다음과 같다.

#include<iostream>
#include<deque>
#include<map>
using namespace std;

deque<char>   answer;
deque<int>    count;

int main() {
    //ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    string given, bomb;

    map<char,int> m;

    cin >> given; 
    cin >> bomb;
    
    for (int i = 0; i < bomb.length(); i++) {
        char now = bomb[i];
        m[now] = i;
    }

    for (int i = 0; i < given.length(); i++) {
        char now = given[i];
        answer.push_back(now);
        if (m.find(now) != m.end())
        {
            int now_i = m[now];
            if (now_i == 0) {
                count.push_back(0);
            }
            else if (!count.empty() && count.back() == now_i-1) {
                count.pop_back();
                count.push_back(now_i);
            }
            else {
                count.clear();
            }
                
            if (!count.empty() && count.back() == bomb.length()-1) {
                count.pop_back();
                for (int i = 0; i < bomb.length(); i++) answer.pop_back();
            }
            
        }
        else {
            count.clear();
        }
    }

    if (answer.empty()) cout << "FRULA";

    while (!answer.empty()) {
        cout << answer.front();
        answer.pop_front();
    }
}

중간에 stdio과 연결을 끊는 코드를 주석처리한 이유는

vscode에서 테스트할 때 왜인지 저 코드를 주석처리 하지 않을 경우

매우 긴 입력을 받을 경우 입력을 받다가 중간에 끊어져 버리기 때문이다.

어차피 입력은 딱 두줄로 받으니 빠른 입력은 필요가 없어서 삭제했다.