글 읽기 - 16% 시간초과

minu452 1년 전 0

16%에서 시간초과가 뜨는데, 코드를 가볍게 짜는 방법이 있나요?

파싱이나 리버스 하는 부분에서 시간초과가 되는 것 같은데... 도와주세요!...!

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

using namespace std;

int T, n;
string p, arr;

deque<string> extractNum(string& a)
{
    deque<string> nums;
    string num="";
    for (int i=0; i<a.size(); i++) {
        if (a[i] != '[' && a[i] != ',' && a[i] != ']') {
            num += a[i];
        }
        else {
            if (num !="") {
                nums.push_back(num);
                num="";
            }
        }
    }    
    return nums;
}

void R(deque<string>& a)
{
    reverse(a.begin(), a.end());
}

void D(deque<string>& a)
{
    a.pop_front();
}

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

    // freopen("5430.txt", "r", stdin);
    cin >> T; 
    for (int tc=0; tc<T; tc++) {
        cin >> p;
        cin >> n;
        cin >> arr;

        deque<string> vv;
        vv = extractNum(arr);
        int i=0;
        for ( ; i<n; i++) {
            if (p[i] == 'R' && p[i+1] != 'R') {
                R(vv);
            }
            else if (p[i]=='R' && p[i+1] == 'R') i+=2;
            else if (p[i] == 'D') {
                if (vv.size() != 0) {
                    D(vv);
                }
            }
        }

        if (vv.size() != 0) {
            // output
            cout << '[';
            for (int i=0; i<vv.size(); i++) {
                if (i == vv.size()-1) cout << vv[i];
                if (vv.size() > 1 && i != vv.size()-1) cout << vv[i] << ",";
            }
            cout << ']' << "\n";
        }
        else {
            cout << "error" << endl;
        }
        
    }
}

pill27211 1년 전 0

리버스 함수의 연산 시간은 당연히 리스트의 길이에 비례합니다. 즉, 덱의 장점이 활용되지 못하고 있습니다.

짝수 번 reverse하면 결국 제자리라는 것을 이용해 보세요.(+아시다시피 덱은 앞과 뒤의 요소 삭제시 복잡도가 상수에 근접합니다.)

그리고 최초 문자열을 파싱하며 덱에 int형으로 요소들을 관리해보는 게 어떨까요?

minu452 1년 전 0

감사합니다! 아래와 같이 바꿔봤습니다. 하지만 리버스를 줄이는 방법이 잘못된 것 같은데, 혹시 좋은 방법이 있을까요?

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

using namespace std;

int T, n;
string p, arr;

deque<int> extractNum(string& a)
{
    deque<int> nums;
    string num="";
    for (int i=0; i<a.size(); i++) {
        if (a[i] != '[' && a[i] != ',' && a[i] != ']') {
            num += a[i];
        }
        else {
            if (num !="") {
                nums.push_back(stoi(num));
                num="";
            }
        }
    }    
    return nums;
}

void R(deque<int>& a)
{
    reverse(a.begin(), a.end());
}

void D(deque<int>& a)
{
    a.pop_front();
}

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

    // freopen("5430.txt", "r", stdin);
    cin >> T; 
    for (int tc=0; tc<T; tc++) {
        cin >> p;
        cin >> n;
        cin >> arr;

        deque<int> vv;
        vv = extractNum(arr);
        
        int i=0;
        for ( ; i<p.size(); i++) {
            if (p[i] == 'R' && p[i+1] != 'R') R(vv);
            else if (p[i]=='R' && p[i+1] == 'R') i+=2;
            else if (p[i] == 'D') {
                if (vv.size() != 0) D(vv);
            }
        }

        if (vv.size() != 0) {
            // output
            cout << '[';
            for (int i=0; i<vv.size(); i++) {
                if (i == vv.size()-1) cout << vv[i];
                if (vv.size() > 1 && i != vv.size()-1) cout << vv[i] << ",";
            }
            cout << ']' << "\n";
        }
        else {
            cout << "error" << endl;
        }
        
    }
}

pill27211 1년 전 2

'D'를 만나기 전까지 등장한 'R'의 개수를 x라고 해봅시다.

이때 x가 만약 짝수라면 결국 덱에서 맨 앞의 원소를 삭제하는 행위(pop_front())와 같고, x가 홀수라면 결국 덱에서 맨 뒤의 원소를 삭제하는 행위(pop_back())와 같겠죠.

즉, 위에서 말씀드렸다시피 reverse(a.begin(), a.end()); 라는 행위 자체가 필요 없다는 것입니다.

그리고 57행과같은 문장은 undefined behavior을 일으킬 수 있는 문장입니다.

minu452 1년 전 0

감사합니다!

해결됐습니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

16% 시간초과

minu452 1년 전 0

pill27211 1년 전 0

minu452 1년 전 0

pill27211 1년 전 2

minu452 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말