9935번: 문자열 폭★발

이게 왜 골드 4밖에 안돼??

사실 요즘 골드문제 해설 없이 푼적이 없다

이번 문제는 악바리로.. 해결

요즘 보이는 내 문제:

1. 논리에 빵꾸가 너무 많음. 마치 base case 없는 재귀함수

1.1 그래서 오류나기 쉬운 특수 케이스들에 많이 걸림

그래서!

1.1은 제출 전 특수 케이스는 뭐가 있을까 생각해보면 됨

1. 논리 / 뼈대까진 괜찮음 살이랑 근육이 문제임.

=> 좀 더 CS적인 생각으로 내가 컴퓨터고 컴퓨터가 나인 경지까지 생각해보기.

추가로 도움은 앳코더 abc394-C에서 많이 얻음.

이거 그리디구나 생각할 수 있도록 해줌. ( 덕분에 $O(N^2)$에서 $O(N)$으로 줄임 )

해설

더보기

스택이나 새로 문자열 하나 만들어서 푸는 것이 정배인듯

나는 이중연결리스트로 풀었다. 그래서 난이도가 높았다 생각했을 수도

기본적인 틀은 abbcca 를 bc로 터치는 예제로 보자.

일단 문자열을 한바퀴 돌며 c를 찾아낸다. 터지는 문자열의 끝!이 핵심. (이유는 잘 생각해보라)

1 c를 찾으면 앞이 b인지 즉 터문인지 확인한다.

2 맞으면 bc 앞 뒤를 맺어서 bc를 스킵하도록 한다. ab -> ca

그다음 bc뒤 c부터 시작 또 c이므로 1, 2를 반복

남은 연결된 문자열은 aa가 된다. 쓰고보니 더 복잡하네 그냥 스택으로 풀도록.. 스택이 속도도 두배는 빠르네

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int prev, next;
};

Node n[1000000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    string s; cin >> s;
    string c; cin >> c;

    for (int i{ 1 }; i < size(s) - 1; i++) {
        n[i].prev = i - 1;
        n[i].next = i + 1;
    }

    n[0].prev = -1;
    n[0].next = 1;
    n[size(s) - 1].prev = size(s) - 2;
    n[size(s) - 1].next = -1;

    bool frula{ false };
    for (int i = size(c) - 1; i < size(s); i++) {
        if (s[i] != c[size(c) - 1]) continue;
        int cidx{ i }; // idx for check
        for (int t{ int(size(c)) - 1 }; t >= 0; t--) {
            if (cidx == -1) break;
            if (!(s[cidx] == c[t])) break;
            if (t == 0) {
                if (n[cidx].prev == -1 && n[i].next == -1) {
                    frula = true;
                }
                else if (n[cidx].prev == -1) {
                    n[n[i].next].prev = -1;
                }
                else if (n[i].next == -1) {
                    n[n[cidx].prev].next = -1;
                }
                else {
                    n[n[cidx].prev].next = n[i].next;
                    n[n[i].next].prev = n[cidx].prev;
                }
            }
            cidx = n[cidx].prev;
        }
    }

    int start{ 0 };
    for (size_t i{ size(s) - 1 }; i >= 1; i--) {
        if (n[i].prev == -1) {
            start = i;
            break;
        }
    }
    int idx{ start };
    if (frula) {
        cout << "FRULA";
    }
    else {
        while (idx != -1) {
            cout << s[idx];
            idx = n[idx].next;
        }
    }
    //cout << "\n";
    //for (int i{ 0 }; i < size(s); i++) {
    //    cout << s[i] << " " << i << " " << n[i].next << " " << n[i].prev << "\n";
    //}
}
/*
ababcc
abc
ababababababcccccc
abc
FRULA
F
a
a
a
c
573573573
57
32767
32767
poipoipoipoi
oi
caaaaaaaaaa
a
oioioioioi
io
ioioioioioi
io


*/