1. 5052 - 문자열 / Vector,Sort

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

입력으로 주어진 전화번호의 목록에서,
한 번호가 다른 번호의 접두어인 경우가 존재하는지를 찾는 문제이다.

위처럼 연속된 숫자로 주어지게 된다.
음... 구현하기 쉬워보인다.

해결

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

using namespace std;

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

    int T, N;
    cin >> T;

    // T = TestCase
    while (T--)
    {
        bool NoFlag = false;
        cin >> N;
        vector<string> Number;

        // 1 전화번호 입력을 받아서 벡터에 저장
        for (int i = 0; i < N; i++)
        {
            string sinput;
            cin >> sinput;
            Number.push_back(sinput);
        }

        // 2 Sort를 진행 - 가장 중요한 부분
        sort(Number.begin(), Number.end());

        // 3 본인과 본인 다음의 것만 비교
        for (int i = 0; i < Number.size() - 1; i++)
		{
			if (Number[i] == Number[i + 1].substr(0, Number[i].size()))
            {
                cout << "NO\n";
                NoFlag = true;
                break;
            }				
		}

        // 4 NoFlag로 출력 구분
        if(NoFlag)
        {
            continue;
        }

        cout << "YES\n";      
    }

    return 0;
}

풀이

        // 2 Sort를 진행 - 가장 중요한 부분
        sort(Number.begin(), Number.end());

우선 크기가 정해진 입력이라서 배열로 받을까 생각했는데,
굳이 배열로 받을 필요가 있을까 싶어서 Vector로 받았고,

Vector로 받았을 때, 모두 하나하나 비교할 수 있지만,
sort기능도 사용할 수가 있어서, 정렬해보았다.

정렬을 한다면, 접두어 비교를 매우 쉽게 할 수 있게 된다.
다음단어랑만 비교하면 되기 때문이다.

if (Number[i] == Number[i + 1].substr(0, Number[i].size()))

위의 코드로 다음 단어랑만 비교하여 출력을 구한다.

앞의 단어부터 비교하는게 있다 ? == vector sort를 생각해본다.

사실 sort가 비용이 많이 드는 줄 알았지만,

위처럼 nLogn밖에 되지 않았다.

문제의 경우에서 10글자자리 문자열이 10000개 주어지는 테스트케이스가 50개 있을 수 있는데,

10000개끼리 비교하는 연산을하면 무조건 시간초과가 날 것이다.
(50까지 곱해서)

하지만 sort작업을 하고, 본인 다음의 것만 딱 한번 비교했기 때문에
시간초과가 나지 않았다.

Sort도 nLogn이라 10000이라고 봐도 무방했다.

2. 12904 - 문자열 / Rev,Era

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

이런 문제인데..
B를 추가하는 조건이 상당히 복잡하다.

우선 원본에서 바뀐문자열을 구하기보다.
바뀐문자열에서 역으로 가는것이 쉬워보인다.

일단 구현해보자.

시도

#include <iostream>
using namespace std;

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

    string S, T;
    cin >> S >> T;

    // T의 맨앞 맨뒤 인덱스
    int sIdx = 0;
    int eIdx = T.length() - 1;

    bool isReversed = false;
    int Idx = eIdx;

    cout << eIdx << "\n";

    while (eIdx - sIdx != S.length() - 1)
    {
        if (isReversed)
        {
            Idx = sIdx;
        }
        else
        {
            Idx = eIdx;
        }

        if (T[Idx] == 'A')
        {
            cout << "Delete A : \n";
            if (isReversed)
            {
                sIdx++;
            }
            else
            {
                eIdx--;
            }

            cout << "reversed? : " << isReversed << "\n";
        }
        else // == 'B'
        {
            cout << "Delete B : \n";
            if (isReversed)
            {
                sIdx++;
                isReversed = false;
            }
            else
            {
                eIdx--;
                isReversed = true;
            }
            cout << "reversed? : " << isReversed << "\n";
        }

        /*
        if((sIdx == eIdx) && S.length()==1)
        {
            cout << "0/0 = " << T[sIdx];
        }
        else
        {
            cout << sIdx << "/" << eIdx << " = " << T.substr(sIdx, eIdx + 1) << "\n";
        }
        */
    }

    if ((sIdx == eIdx) && S.length() == 1)
    {
        if (T[sIdx] == S[0])
        {
            cout << 1;
            return 0;
        }
        else
        {
            cout << 0;
            return 0;
        }
    }

    cout << T.substr(sIdx, eIdx + 1) << "\n"
         << S << "\n";
    if (T.substr(sIdx, eIdx + 1) == S)
    {
        cout << 1;
        return 0;
    }
    else
    {
        cout << 0;
        return 0;
    }

    return 0;
}

AB
ABB
위의 반례를 해결하지 못한다.

해결

#include <iostream>
#include <algorithm>

using namespace std;

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

    string S, T;
    cin >> S >> T;

    while(S.length() != T.length())
    {
        if(T[T.length()-1] == 'B')
        {
            T.erase(T.length()-1);
            reverse(T.begin(), T.end());
            //cout << "B : ";
        }
        else
        {
            T.erase(T.length()-1);
            //cout << "A : ";
        }

        //cout << "T : " << T << "\n";
    }

    //cout << S << " / " << T <<"\n";
    if(S==T)
    {
        cout << 1;
    }
    else
    {
        cout << 0;
    }
    return 0;   
}

풀이

그냥 단순히 역계산을 한다.
reverse와 erase를 사용하였다.

reverse는 시간복잡도가 O(n)이다.
erase는 삭제하고, 뒤의 원소들을 당겨야하지만,
맨 마지막 원소라면 O(1)의 복잡도밖에 되지 않는다.

문자열의 삭제가 맨 뒤의 값이라면 망설이지말고 erase를 사용한다.

그리고 잘 보니 빡빡한 문제도 아니었다.

3. 16120 - 문자열 / Bomb

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

문제가 어려워질수록 문자열만 다루는 문제는 없었다.
그래서 이 문제를 마지막으로 문자열을 마치려고 한다.

조건은 딱 2가지이다.

• p는 PPAP 문자열
• p는 ppap로 바뀔 수 있고, 이것도 PPAP 문자열

해결

#include <iostream>
#include <stack>
using namespace std;

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

    string s;
    cin >> s;

    stack<char> answer;

    for (int i = 0; i < s.size(); i++)
    {
        answer.push(s[i]);
        if (s[i] == 'A' && i + 1 < s.size())
        {
            if (s[i + 1] == 'P') // 즉 A일때, 뒤의 글자가 P라면, 앞이 PP인지 확인
            {
                answer.pop(); // 들어가있는 A를 뺌

                // 앞의 PP를 비교해야하는데 없으면 안됨
                if (answer.size() < 2)
                {
                    cout << "NP";
                    return 0;
                }

                // A가 나오면 무조건 앞의 PP가 나와야만 함
                for (int t = 0; t < 2; t++)
                {
                    if (answer.top() == 'P')
                    {
                        answer.pop();
                    }
                    else
                    {
                        cout << "NP";
                        return 0;
                    }
                }
            }
            else // A다음에 A가 나오는 경우 PPAP문자열이 절대 될 수 없다.
            {
                cout << "NP";
                return 0;
            }
        }
    }

    if (answer.size() != 1 || answer.top() == 'A')
    {
        cout << "NP";
        return 0;
    }
    else
    {
        cout << "PPAP";
    }

    return 0;
}

풀이

PPAP 문자열이 되기 위해선,
A가 중요한 요소였다.

차례차례 stack에 쌓고 있을 떄,
A를 기준으로 앞에 P2개, 다음 P1개가 없다면,
바로 NP를 출력하면 된다.

정상종료시에는 PPAP를 출력

문자열에서 특정 문자열을 찾고 연쇄삭제하는
이른바 Bomb문자열 문제의 경우,
Stack을 사용하는 것이 편리하다는 것을 깨달았다.

일단 이것으로 실버~골드4까지의 문자열 문제는 훑어보았다.
골드 3부터는 LCS같은 문제가 나오는데, DP나 Tree까지 이용해야하는
다중 카테고리의 문제들이 출제된다.

따라서 단일 카테고리 먼저 완료한 뒤, 다시 풀어보기로 한다.
다음 주제는 BruteForce(완전탐색) / DP를 다룰 생각이다.