인프런 커뮤니티 질문&답변

안녕하세요 선우님 ㅎㅎ

문제 범위를 볼까요?

단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

단어의 길이는 최대 10만입니다.

        while (!my_s.empty())
        {
            if (my_s.size() == 1)
            {
                break;
            }
            char a = my_s.back();
            my_s.pop_back();

이 코드를 보면 해당 dequeue가 빌 때까지 계속해서 back, pop_back을 반복하는데요. 최대치로 잡으면 n / 2 정도가 되겠죠?

즉, n / 2정도의 시간복잡도가 추가되서 5만정도가 +가 됩니다.

어차피 문자열입력받아서 순회만해도 최대 10만이기 때문이고 이정도는 문제 없을것 같습니다.

네 맞습니다.

보통 시간복잡도를 계산할 때 + 정도는.. 사실 괜찮긴 합니다. 그래서 선우님 코드가 막 그렇게 시간초과가 많이 나오는 코드는 아닙니다.

그러나

코드를 보면 뒤에 2개를 빼서 확인하고 아니라면 맨앞으로 순서를 바꾸는 로직이 있습니다.

이렇게 순서를 바꾸는데 이렇게 해도 계속해서 비지 않은 경우는 어떨까요?

        while (!my_s.empty())

이렇게 디버깅코드를 작성해서 돌려보시겠어요?

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N;
    int cnt = 0;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        deque<char> my_s;
        string str;
        cin >> str;

        for (int i = 0; i < str.length(); i++)
        {
            my_s.push_back(str[i]);
        }

        while (!my_s.empty())
        {
        cout << my_s.size() << '\n';
            if (my_s.size() == 1)
            {
                break;
            }
            char a = my_s.back();
            my_s.pop_back();

            char b = my_s.back();
 
            if (a == b)
                my_s.pop_back();
            else
                my_s.push_front(a);
        } 

        if (my_s.empty())
            cnt++;
    }
    cout << cnt;
    return 0;
}

1

ABAB

를 하면 무한루프가 발생됩니다.

이 때문에 시간초과가 발생되게 됩니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.