대략 2일동안 문자열을 풀어보았는데,
골드까지 아직 가지 못했다.

그런데 문자열을 막상 풀어보니,
골드가 실버의 상위호환 문제는 또 아니라는 생각이 들었다.
문자열 문제의 범위가 넓다보니, 모든 문제들이 문자열의 특정 부분만 건드리게 되고,
따라서 문자열 문제는 그냥 가리지않고 많이 풀어보는게 오히려 도움이 될 것 같다.

https://www.acmicpc.net/problem/9251

이건 DP와 문자열의 중간으로 남겨둔다.
DP구현할 때, 다익스트라도 복습할 것

https://www.acmicpc.net/problem/14725

이건 구현문제인데 구조가 복잡해서 나중에 꼭 풀어본다.

문제는 아래 문제들 중에서 풀어보려고 한다.
기준은 실버2~1~골드 문제들을 유명한 순으로 정렬해두었다.
https://www.acmicpc.net/problemset?sort=ac_desc&tier=9%2C10%2C11%2C12%2C13%2C14%2C15&algo=158&algo_if=and

1. 1541 - 문자열

https://www.acmicpc.net/problem/1541

+ / - / 괄호 3가지의 기호가 있는 식에서 최소값을 구하기 위해
기호를 그려넣는다는 문제이다.

처음에는 이해가 되지 않았다.
왜냐면 +-식에 아무리 괄호를 넣는다고 해도 값은 변함이 없기 때문이다.

하지만 위의 예제를 보니 깨달았다.

minus 바로 뒤에 괄호를 씌우면 된다.

그렇다면
minus부터 minus까지를 파싱하는 알고리즘을 짜고,
파싱된 값의 크기가 가장 큰 것을 괄호를 씌운다면 될 것 같다.

구현해보자.
음.. -1+2+3-1+100 이라고 한다면,
생각한 나의 알고리즘에선 6 101 두개로 나뉜다..
음..

풀면서 문제를 잘못 이해하고 있다고 느꼈다.
괄호는 여러개가 존재해도 상관없다.

왜냐? 그냥 적절히 치라고 했기 때문이다.
단수도 복수도 적혀있지 않으므로 복수라고 생각한다.

그렇다면
-1+2+3-1+100 문제도 해결된다.
-(1+2+3)-(1+100) 그냥 - 사이의 것들을 괄호치면 되는 것이다.
-6 -101 = -107
문제가 너무 쉬워졌다.
만약 하나만 칠 수 있었다면, 내가 생각한 것처럼
-와 - 사이의 식을 더한 값들의 최대값을 비교하고,
해당 값만 -화 시키고,
나머지 값은 그냥 식대로 더해야했다.

해결

#include <iostream>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    int totalSum = 0;
    string strNum = "";  // 글자로부터 숫자를 만들기 위한 용도
    bool isInMinus = false; // -가 한번 나오면, 그 뒤의 숫자는 모두 -시킨다.

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] != '+' && s[i] != '-')
        {
            strNum += s[i];

            if (i == s.size() - 1)
            {
                int num = stoi(strNum);
                if (isInMinus)
                {
                    totalSum -= num;
                }
                else
                {
                    totalSum += num;
                }
            }
        }
        
        if(s[i] == '+' || s[i] == '-')
        {
            int num = stoi(strNum); // 여태까지의 문자를 숫자로 변환

            if (s[i] == '+')
            {
                if (isInMinus)
                {
                    totalSum -= num;
                }
                else
                {
                    totalSum += num;
                }
            }
            else if (s[i] == '-')
            {
                if(!isInMinus)
                {
                    totalSum += num;
                }
                else
                {
                    totalSum -= num;
                }
                isInMinus = true;
            }

            strNum = "";
        }
    }
    cout << totalSum;

    return 0;
}

풀이

문제가 허술했다.
minus기호가 한 번 나오면, 그 다음의 수들은 기호에 상관없이
모두 빼주면 된다.

따라서 해당 Flag를 isInMinus로 두었다.

그리고 상황에 맞게 계산하도록 구현만 하면 끝.

2. 5430 - 문자열 / 구현

https://www.acmicpc.net/problem/5430

문제가 해석하기 어렵지는 않았다.

R이면 뒤집고, D면 맨 앞의 원소를 삭제한다.
D를 할 수 없다면, error를 출력한다.

가장 어려운 부분은 아마 데이터파싱하는 부분일 것이다.

배열의 입력이 위처럼 주어진다.

적절히 파싱하고, 적절한 자료구조에 담으면 끝날 것 같다.

시도 1

왜 이 stoi는 안될까
생각해보니, 가장 마지막 예제가 []였다.
아무 수도 없는 것이다. 따라서 빈 문자열을 int형으로 만드려한 것이었다.

수정한다.

시도 2

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        string command;
        cin >> command;

        int n;
        cin >> n;

        string arr;
        cin >> arr;

        // bool isReversed = false;
        bool isError = false;

        // 1 Data Parsing
        vector<int> realArray;
        string tmpString = "";
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] == '[')
            {
                continue;
            }
            else if (arr[i] == ']')
            {
                if (tmpString != "")
                {
                    int num = stoi(tmpString);
                    //cout << "input : " << num << "\n";
                    realArray.push_back(num);
                }
            }

            if (arr[i] == ',')
            {
                int num = stoi(tmpString);
                //cout << "input : " << num << "\n";
                realArray.push_back(num);
                tmpString = "";
                continue;
            }

            tmpString += arr[i];
        }

        for(int i=0;i<command.size();i++)
        {
            if(command[i] == 'R')
            {
                reverse(realArray.begin(), realArray.end());
            }
            else if(command[i] == 'D')
            {
                if(realArray.size()<1)
                {
                    cout << "error\n";
                    isError = true;
                    break;
                }
                realArray.erase(realArray.begin()+0);
            }
        }

        if(isError)
        {
            continue;
        }

        int idx=0;
        cout << "[";
        for(auto v : realArray)
        {
            if(idx==realArray.size()-1)
            {
                cout<< v << "]\n";
                break;
            }
            cout << v << ",";
            idx++;
        }
    }

    return 0;
}

시간초과 에러가 났다.
가장 의심이 되는 부분은

이부분이다.
역시나 Reverse와 Erase연산이 버거워보인다.

그 중 비용이 더 높다고 생각하는 Reverse부터 바꿔본다.

시도 3

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        string command;
        cin >> command;

        int n;
        cin >> n;

        string arr;
        cin >> arr;

        bool isReversed = false; // reverse를 수행할 것
        bool isError = false;

        // 1 Data Parsing
        vector<int> realArray;
        string tmpString = "";
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] == '[')
            {
                continue;
            }
            else if (arr[i] == ']')
            {
                if (tmpString != "")
                {
                    int num = stoi(tmpString);
                    // cout << "input : " << num << "\n";
                    realArray.push_back(num);
                }
            }

            if (arr[i] == ',')
            {
                int num = stoi(tmpString);
                // cout << "input : " << num << "\n";
                realArray.push_back(num);
                tmpString = "";
                continue;
            }

            tmpString += arr[i];
        }

        for (int i = 0; i < command.size(); i++)
        {
            if (command[i] == 'R')
            {
                if (isReversed)
                {
                    isReversed = false;
                }
                else
                {
                    isReversed = true;
                }
            }
            else if (command[i] == 'D')
            {
                if (realArray.size() < 1)
                {
                    cout << "error\n";
                    isError = true;
                    break;
                }

                if (isReversed)
                {
                    realArray.erase(realArray.end() - 1);
                }
                else
                {
                    realArray.erase(realArray.begin() + 0);
                }
            }
        }

        if (isError)
        {
            continue;
        }

        cout << "[";
        if (isReversed)
        {
            for (int i = realArray.size() - 1; i >= 0; i--)
            {
                cout << realArray[i];
                if (i == 0)
                {
                    cout << "]\n";
                    break;
                }
                cout << ",";
            }
        }
        else
        {
            for (int i = 0; i < realArray.size(); i++)
            {
                cout << realArray[i];
                if (i == realArray.size()-1)
                {
                    cout << "]\n";
                    break;
                }
                cout << ",";
            }
        }

        // 문자가 0개인 경우, 예외처리
        if(realArray.size()==0)
        {
            cout << "]\n";
        }
    }

    return 0;
}

역시 reverse만 바꾸니 시간초과가 난다.
erase까지 바꿔야 될 것 같다.

시도 4

수정을 했는데,

1
D
0
[]

이 예제에서 문제가 생긴다.
왜?

        for (int i = 0; i < command.size(); i++)
        {
            if (command[i] == 'R')
            {

잘되던 위의 구문에서 segmentation오류가 났다.
왜?

int realArray[n] = {0,};

위처럼 초기화 하던 구문이 문제였다.
n이 0이면 위처럼 초기화할 수 없기 때문이다.
이상한 부분에서 에러가 발생한다면, 그 위쪽 라인을 파악하는 것이 필요했다.

해결

#include <iostream>
#include <string>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;

    while (T--)
    {
        string command;
        cin >> command;

        int n;      //해당 값이 0이면 문제가 생김
        cin >> n;

        string arr;
        cin >> arr;

        bool isReversed = false; // reverse를 수행할 것
        bool isError = false;

        // 1 Data Parsing
        int startIdx = 0;
        int endIdx = n-1;
        int Idx = 0;
        int realArray[n];


        string tmpString = "";
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] == '[')
            {
                continue;
            }
            
            if (arr[i] == ']')
            {
                if (tmpString != "")
                {
                    int num = stoi(tmpString);
                    // cout << "input : " << num << "\n";
                    realArray[Idx] = num;
                }
                continue;
            }

            if (arr[i] == ',')
            {
                int num = stoi(tmpString);
                // cout << "input : " << num << "\n";
                realArray[Idx] = num;
                Idx++;
                tmpString = "";
                continue;
            }
            tmpString += arr[i];
        }

        // 인덱스 수정으로 삭제효과
        startIdx = 0;
        endIdx = n-1;

        // command line에 맞게 수정
        for (int i = 0; i < command.size(); i++)
        {
            if (command[i] == 'R')
            {
                if (isReversed)
                {
                    isReversed = false;
                }
                else
                {
                    isReversed = true;
                }
            }
            
            if (command[i] == 'D')
            {
                if (startIdx > endIdx || endIdx == -1)
                {
                    cout << "error\n";
                    isError = true;
                    break;
                }

                if (isReversed) //1 reverse 된 상황에서 맨 앞의 것을 뺀다면,
                {
                    endIdx --;  // 그냥 뒤 인덱스를 하나 줄인다.
                }
                else            //2 그냥 상태에서 맨 앞의 것을 뺀다면,
                {
                    startIdx ++; // 그냥 앞 인덱스를 하나 늘린다.
                }
            }
        }

        // Error라면 출력을 건너뜀
        if (isError)
        {
            continue;
        }

        // 출력 - reverse라면, index를 거꾸로 출력
        cout << "[";
        if (isReversed)
        {
            for (int i = endIdx; i >= startIdx; i--)
            {
                cout << realArray[i];
                if (i == startIdx)
                {
                    cout << "]\n";
                    break;
                }
                cout << ",";
            }
        }
        else
        {
            for (int i = startIdx; i <= endIdx; i++)
            {
                cout << realArray[i];
                if (i == endIdx)
                {
                    cout << "]\n";
                    break;
                }
                cout << ",";
            }
        }

        // 문자가 0개인 경우, ]를 표시할 수 없으므로 이렇게 예외처리
        if(startIdx > endIdx)
        {
            cout << "]\n";
        }
    }
    

    return 0;
}

풀이

https://www.acmicpc.net/board/view/122205
위의 반례들을 싹다 맞춰보니 풀렸다.

vector로 구현했다가 안되어서 배열로 바꿨을 뿐인데,
이렇게 구현에 반례들이 많고 오래걸릴지 몰랐다.

벡터를 사용하지 않고, 실제로 원소를 지우지 않고 사용하는 방식을 택했다.

구상은 어렵지 않았는데 구현이 어려웠다.
반례가 많았기 때문이다.
하.. 시간이 많이 들었다.

만약 백준의 반례가 없었더라면 혼자서 반례를 생각해낼 수 있었을까?
혼자 생각해냈다면 시간이 얼마나 더 걸렸을까..

코딩테스트는 숙련되어야한다는데, 왕도가 없음을 다시한번 느끼고,
역시 계속 꾸준히 공부해야만하겠다는 생각이 드는 문제였다.

3. 9935 - 문자열 / Stack / Bomb

https://www.acmicpc.net/problem/9935

문자열과 폭발문자열이 주어진다.
문자열 내에 폭발문자열이 있다면 폭발한다(= 해당 문자열이 사라지고 양옆이 붙여진다)
폭발한 문자열에 폭발문자열이 또 존재한다면 또 폭발한다.

최종적으로 폭발할 것이 없는 문자열을 구하면 된다.

어떻게 효율적으로 구해야할지 방법이 생각나지 않는다.
단순히 for문을 연속해서 쓰는건 아닐것 같은데..
일단 구현해본다.

시도

#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    string search;
    cin >> search;

    int sLen = s.length();
    int schLen = search.length();


    //cout << "[ BOMB ]\n";
    string tmpString = s;
    while (true)
    {
        string frontS = "";
        string backS = "";

        int idx = tmpString.find(search);

        // 탈출조건
        if (idx == -1)
        {
            break;
        }
        else
        {
            if (idx != 0)
            {
                frontS = tmpString.substr(0, idx);
                backS = tmpString.substr(idx + schLen, s.size() - 1);
            }
            else
            {
                backS = tmpString.substr(idx + schLen, s.size() - 1);
            }
        }
        tmpString = (frontS + backS);

        //cout << tmpString <<"\n";
    }

    if(tmpString=="")
    {
        cout << "FRULA";
    }

    cout << tmpString;

    return 0;
}

substr과 문자열의 함침을 무작정 이용해보았다.
예제, 반례 출력이 모두 잘 되지만, 시간초과가 떴다.

골드부터는 항상 시간초과를 의심해봐야만 한다.

시도 2

#include <iostream>
#include <stack>

using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    string s;
    cin >> s;

    string b;
    cin >> b;

    int sLen = s.length();
    int bLen = b.length();

    stack<char> answer;

    int combo = 0;
    for (int i = 0; i < sLen; i++)
    {
        answer.push(s[i]);
        if (s[i] == b[combo])
        {
            combo++;
        }
        else
        {
            combo = 0;
            if (s[i] == b[combo])
            {
                combo++;
            }
        }

        if (combo == bLen)
        {
            for (int i = 0; i < bLen; i++)
            {
                answer.pop();
            }

            if (answer.size() == 0 && i == sLen -1)
            {
                cout << "FRULA";
                return 0;
            }

            combo = 0;
            if (answer.size() !=0 && answer.top() == b[combo])
            {
                combo++;
            }
        }
    }

    stack<char> reverseStack;
    int aSize = answer.size();

    while (aSize--)
    {
        reverseStack.push(answer.top());
        answer.pop();
    }

    int rSize = reverseStack.size();
    while (rSize--)
    {
        cout << reverseStack.top();
        reverseStack.pop();
    }

    return 0;
}

틀렸다.

abaabcdbcdcd
abcd

정답: FRULA

위의 반례가 존재한다.
현재 내 코드는 abcd가 사라지면, 마지막 b를 처음으로 본다.

음... 어떻게 수정해야할까..
마지막인 경우에만 비교해야할까?

Bomb을 뒤에서부터 비교한다.
그렇게 된다면 굳이 앞의 것을 기억할 필요가 없게된다.

해결

#include <iostream>
#include <stack>
#include <queue>

using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    string str;
    string bomb;

    cin >> str >> bomb;

    int slen = str.length();
    int blen = bomb.length();

    stack<char> answer;
    stack<char> chkBomb; 
    int idx = 0;

    for(int i=0;i<slen;i++)
    {
        answer.push(str[i]);

        // 현재 글자가 bomb의 마지막 글자와 같다면,
        if(str[i]==bomb[blen-1] && answer.size()>=blen)
        {
            // 뒷글자부터 앞까지 blen만큼 비교한다.
            for(int k=blen-1;k>=0;k--)
            {
                // 맨뒤와 bomb의 뒤가 같으면 pop연산을 한다. 
                // 아닐 경우를 대비해서 queue에 push한다.
                if(bomb[k]==answer.top())
                {
                    chkBomb.push(answer.top());
                    answer.pop();

                    // 끝까지 갔다면 기억하고 있을 필요가 없으므로 삭제
                    if(k==0)
                    {
                        while(!chkBomb.empty())
                        {
                            chkBomb.pop();
                        }
                    }
                }
                // 아닐경우, 모든 값을 다시 push한다.
                else
                {
                    while(!chkBomb.empty())
                    {
                        answer.push(chkBomb.top());  
                        chkBomb.pop();
                    }
                }
            }
        }
    }

    int aSize = answer.size();

    // 예외처리
    if(aSize == 0)
    {
        cout << "FRULA";
        return 0;
    }

    // 출력을 위해서 stack을 뒤집는다
    stack<char> reverseStack;
    while (aSize--)
    {
        reverseStack.push(answer.top());
        answer.pop();
    }

    // 진짜 출력
    int rSize = reverseStack.size();
    while (rSize--)
    {
        cout << reverseStack.top();
        reverseStack.pop();
    }

    return 0;   
}

풀이

stack을 사용하고 있는데 바보같이 bomb을 앞에서부터 비교하였다.

뒤의 글자부터 차근차근 빼면서 확인하면 되는 문제였다.
조건이 어렵지도 않았고,
stack을 사용한다는 아이디어를 떠올릴 수 있고,
stack을 사용하므로 top, pop을 사용하여 bomb과 비교한다는 생각만 할 수 있다면,
쉬운 문제였을 것이다.