[백준] 5430: AC

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

5430번: AC

 

구현 문제이다. 

16%에서 시간초과가 계속해서 발생하였다.

16% TC 시간초과

문제의 입력으로 주어진 문자열이 매우 길 수 있고(10만 문자) 연산 횟수가 10만 번이기 때문에 시간초과가 발생할 수 있다.

내 경우에는 split 함수에서 매번 구분자(delimeter)를 찾고 문자를 split 하는 과정에서 시간초과가 발생했다.

split 함수 구현시 find, erase를 이용하지않고, stringstream과 getline을 이용하니 시간초과 문제가 해결되었다.

 

find와 erase를 이용한 split (시간초과 코드)

vector<int> split(string input, string d){
    vector<int> ret;
    long long pos=0;
    string token = "";
    while((pos=input.find(d)) != string::npos){
        token = input.substr(0, pos);
        ret.push_back(stoi(token));
        input.erase(0, pos+d.length());
    }
    ret.push_back(stoi(input));
    return ret;
}

- 매 반복마다 문자열의 내용을 수정(erase)하고 새로운 문자열을 생성(substr)한다.

- 추가적인 메모리 할당과 복사 작업을 발생시킨다.

- 매번 문자열에서 delimeter가 있는지 확인한다(find).

stringstream과 getline을 이용한 split

vector<int> split(const string& input) {
    vector<int> ret;
    stringstream ss(input.substr(1, input.length() - 2)); // 대괄호 제거
    string token;

    while (getline(ss, token, ',')) {
        if (!token.empty()) {
            ret.push_back(stoi(token));
        }
    }
    return ret;
}

- 입력 문자열을 스트림으로 변환한 다음(stringstream) 필요한 부분만 읽어들인다(getline).

- 문자열을 한번만 순회하면서 필요한 부분을 추출한다.

 

=> stringstream과 getline을 이용한 split이 메모리 사용과 복잡도 측면에서 훨씬 우수하다. (시간복잡도도 감소!)

코드

#include <bits/stdc++.h>
using namespace std;

int t, n;
vector<int> num;        
string s1, s2;
vector<int> split(const string& input) {
    vector<int> ret;
    stringstream ss(input.substr(1, input.length() - 2)); // 대괄호 제거
    string token;

    while (getline(ss, token, ',')) {
        if (!token.empty()) {
            ret.push_back(stoi(token));
        }
    }
    return ret;
}
int main(){
    cin.tie(0); ios_base::sync_with_stdio(false); cout.tie(0);
    // 1. 입력받기
    cin >> t;
    while(t--){
        // 초기화
        num.clear();
        int lp=0;
        cin >> s1 >> n >> s2;
        // 입력값 처리
        num = split(s2);
        int rp = n-1;
        bool reverse = false;
        // 2. 작업 수행
        for(int i=0;i<s1.length();i++){
            if (lp>rp+1) {
                break;
            }
            if (s1[i]=='R'){
                reverse = !reverse;
            } 
            else if(s1[i]=='D'){
                if(reverse){
                    rp--;
                } else lp++;
            }
        }
        if(lp>rp+1){
            cout << "error" << "\n";
        } 
        else{
            // 정답 출력
            cout << "[";
            if (lp==rp+1);
            else if(reverse){
                for (int i=rp;i>lp;i--) cout << num[i] << ",";
                cout << num[lp];
            }
            else{
                for (int i=lp;i<rp;i++) cout << num[i] << ",";
                cout << num[rp];
            } 
            cout << "]\n";
        }
    }
}

 

 

 

앞으로는 java로 풀 예정이다.

c++로 푸는데 적응이 되었지만, java를 앞으로 더 많이 사용할 것 같기 때문이다.