글 읽기 - 시간 초과가 어디서 나오는걸까요.. 정말 괴롭습니다 ㅠ

samgkgkgk 2년 전 0

우선 풀이는 이렇습니다.

1) 덱 3개를 준비함

deq, l_deq, r_deq

2) 문자열 S를 deq에 옮겨담음

3) L명령이 주어진 경우

l_find(l_deq, deq, w)함수 호출

deq의 앞 원소부터 차례대로 l_deq에 옮겨담음

이때 l_deq에 W가 있는지를 확인하고 W를 l_deq에서 없앰 -> R명령의 경우도 마찬가지..

4) R L 명령이 반복되다보면 결국 deq은 비어있게 되는데 이 경우에는 l_find(l_deq, r_deq, w)와 r_find(l_deq, r_deq, w)함수를 호출

5) 모든 명령이 종료되면 최종적으로 모든 덱들에 w가 들어있는지 확인한 후 결과값 출력.

근데 이렇게 풀면 9퍼센트 대에서 시간초과가 발생합니다.. 문제가 덱을 이용하는 풀이인데.. 덱들 사이에서의 원소 이동을 이보다 더 줄일 방법이 있을까요 ㅠㅠ 이것만 며칠째 고민하는지 모르겠습니다.. 10번가까이 제출하고 계속 실패하니깐 미칠것같네요 ㅠㅠ

#include <iostream>
#include <deque>

int cnt = 0;
using namespace std;

bool l_find(deque<char>& l_deq, deque<char>& r_deq, const string& W){
    int w_size = (int) W.size();
    bool found = false;
    while(!r_deq.empty()){
        auto curr = r_deq.front();
        l_deq.emplace_back(curr);
        r_deq.pop_front();
        
        //l_deq에 w의 사이즈 이상의 원소가 쌓이고 아직 한 번도 w가 발견되지 않은경우
        //l_deq에서 w를 찾는다 => 이는 r_find에서도 동일함
        if(l_deq.size() >= w_size && curr == W[w_size - 1] && !found){
            deque<char> tmp;
            tmp.emplace_front(l_deq.back());
            l_deq.pop_back();
            
            int j = 2;
            for(; j <= w_size; j++){
                auto next = l_deq.back();
                l_deq.pop_back();
                tmp.emplace_front(next);
                
                if(next != W[w_size - j]){
                    while(!tmp.empty()){
                        l_deq.emplace_back(tmp.front());
                        tmp.pop_front();
                    }
                    break;
                }
            }
            if(j > w_size){
                found = true;
                cnt++;
            }
        }
        if(found)
            break;
    }
    return found;
}

bool r_find(deque<char>& l_deq, deque<char>& r_deq, const string& W){
    int w_size = (int) W.size();
    bool found = false;
    while(!l_deq.empty()){
        auto curr = l_deq.back();
        r_deq.emplace_front(curr);
        l_deq.pop_back();
        
        if(r_deq.size() >= w_size && curr == W[0] && !found){
            deque<char> tmp;
            tmp.emplace_back(r_deq.front());
            r_deq.pop_front();
            
            int j = 1;
            for(; j < w_size; j++){
                auto next = r_deq.front();
                r_deq.pop_front();
                tmp.emplace_back(next);
                
                if(next != W[j]){
                    while(!tmp.empty()){
                        r_deq.emplace_front(tmp.back());
                        tmp.pop_back();
                    }
                    break;
                }
            }
            if(j >= w_size){
                found = true;
                cnt++;
            }
        }
        if(found)
            break;
    }
    return found;
}

bool final_check(deque<char>& l_deq, deque<char>& r_deq, const string& W){
    bool found = false;
    
    found = l_find(l_deq, r_deq, W);
    while(!l_deq.empty()){
        cout << l_deq.front();
        l_deq.pop_front();
    }
    return found;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    string W, S;
    cin >> W >> S;
    
    int T;
    cin >> T;
    
    deque<char> l_deq, r_deq, deq;
    for(auto& i: S){
        deq.emplace_back(i);
    }
    
    for(int i = 0; i < T; i++){
        char c;
        cin >> c;
        
        switch(c){
            case 'L':{
                if(!deq.empty()){
                    l_find(l_deq, deq, W);
                }
                else{
                    l_find(l_deq, r_deq, W);
                }
                break;
            }
            case'R':{
                if(!deq.empty()){
                    r_find(deq, r_deq, W);
                }
                else{
                    r_find(l_deq, r_deq, W);
                }
                break;
            }
        }
    }
    
    cout << cnt << "\n";
    
    bool found;
    if(!deq.empty()){
        found = final_check(l_deq, deq, W);
        
        if(found)
            cout << W;
        
        bool tmp_found = final_check(deq, r_deq, W);
        
        if(tmp_found)
            cout << W;
        
        while(!r_deq.empty()){
            cout << r_deq.front();
            r_deq.pop_front();
        }
        
        found |= tmp_found;
        cout << "\n";
    }
    
    else{
        found = final_check(l_deq, r_deq, W);
        cout << "\n";
    }
    
    if(found)
        cout << "You Lose!\n";
    
    else
        cout << "Perfect!\n";
    return 0;
}

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

문제

문제

출처

ICPC

시간 초과가 어디서 나오는걸까요.. 정말 괴롭습니다 ㅠ

samgkgkgk 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말