[ C++/cpp ] 백준 (5430 AC) ⭐구현, 덱

백준 5430번 AC

(골드 5)

 

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

 

 

 

 

 

(정답 코드)

#include <iostream>
#include <deque>

using namespace std;

string solution(string &p, int &n, string &arr) {
    
    deque<int> dq;
    string ans = "[";
    string num = "";
    bool is_reverse = false;
    
    // 숫자 배열 벡터에 차례로 저장
    for(int i=1; i<arr.length()-1; i++) {
        while(arr[i]!=',' && arr[i]!=']') { // 구분자 나올때까지 i++
            num += arr[i];
            i++;
        }
        dq.push_back(stoi(num));
        num = "";
    }
    
    // RD 명령 수행
    for(int i=0; i<p.size(); i++) {
        // reverse
        if(p[i]=='R') { 
            is_reverse = !is_reverse;
        } 
        // delete
        else { 
            if(dq.empty()) { // 더이상 지울 요소가 없다면 에러 출력
                return "error";
            }
            
            is_reverse ? dq.pop_back() : dq.pop_front() ;
       }
    }
    
    
    // 최종 배열 담기
    if(is_reverse) {
         while (!dq.empty()) {
            ans+= to_string(dq.back());
            dq.pop_back();
            if(dq.empty()) {
                break;
            }
            ans += ',';
        }
    } else {
         while (!dq.empty()) {
            ans+= to_string(dq.front());
            dq.pop_front();
            if(dq.empty()) {
                break;
            }
            ans += ',';
        }
    }
    
    
    return ans+']';
    
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int t, n;
    string p;
    string arr;
    
    cin >> t;
    
    while(t--) {
        cin >> p >> n >> arr;
        cout << solution(p, n, arr) << '\n';
    }

    return 0;
}

 

 

📖 트러블 슈팅

1. 문자열 파싱 오류

구분자 ',' 기준으로 끊어 입력받기

### 수정 전 ### 
    for(int i=1; i<2*n; i+=2) {
        v.push_back(arr[i]);
    }
    
    
### 수정 후 ### 
    for(int i=1; i<arr.length()-1; i++) {
        while(arr[i]!=',' && arr[i]!=']') { // 구분자 나올때까지 i++
            num += arr[i];
            i++;
        }
        v.push_back(stoi(num));
        num = "";
    }

 숫자 배열을 입력해주는 방식이 특이했는데 쉼표를 구분자로 숫자값을 받아야한다. 한자리 수만 삽입되는 게 아니고 [10,20] 이런식일 수도 있는데.. 근데 간과하고 첨에 홀수 번 스트링의 인덱스만 취급해서 틀림..ㅋㅋ 졸린가...? 

 

 

2. 시간 초과 해결하기

매번 벡터를 뒤집지말고, flag 변수로 뒤집힘 여부 표시만 하기

 

  매순간 reverse 함수로 벡터를 실제로 뒤집었다. 근데 뭐 시뮬레이션 할 필요 없이 단순히 지우고 뒤집는 연산 뿐이니, 그래서 그냥 뒤집음 상태를 bool타입으로 저장해두는 방식으로 바꿈.

- reverse : 원본 벡터는 그대로 두고 뒤집힘 여부에 따라 출력 시 인덱스만 정방향/역방향 순회하면 된다.

- delete : 뒤집힘 여부에 따라 삭제 시 맨 앞에, 맨 뒤에 둘 중 하나를 지우면 된다. 

 

### 수정 전 ### 실제로 벡터를 reverse 함수로 뒤집음.
    for(int i=0; i<p.size(); i++) {
        // reverse
        if(p[i]=='R') { 
            reverse(v.begin(), v.end()); // 벡터 뒤집기
        } 
        // delete
        else { 
            if(v.empty()) { // 더이상 지울 요소가 없다면 에러 출력
                return "error";
            }
            v.erase(v.begin()); // 첫번째 요소 삭제
       }
    }
    
    
### 수정 후 ### 실제로 뒤집지 않고 is_reverse로 뒤집힘 여부만 체크해놓고 삭제 연산도 이를 토대로 한다.
    for(int i=0; i<p.size(); i++) {
        // reverse
        if(p[i]=='R') { 
            is_reverse = !is_reverse;
        } 
        // delete
        else { 
            if(v.empty()) { // 더이상 지울 요소가 없다면 에러 출력
                return "error";
            }
            
            is_reverse ? v.erase(v.end() -1) : v.erase(v.begin()) ;
       }
    }

 

 

 

3. 더 빠른 코드 ?

- 삭제 연산 시간 단축을 위해 deque 사용하기

맞긴 했는데 너무 오래걸리네 더 효율화할 순 없을까? 

 

기존 코드 시간이 너무 오래 걸리길래, 문제가 뭘까 했더니 벡터의 erase였다.

벡터는 끝 요소 삭제는 상관없지만, 중간이나 앞에서 요소를 삭제하면 그 뒤의 모든 요소를 당겨서 이동시켜야 하므로 O(n) 시간 복잡도를 가진다. 그래서 erase가 시간을 왕창 잡아먹는것. 그래서 ... deque를 썼다. 덱은 양쪽 끝에서 다 삭제가 O(1)의 시간 복잡도를 갖는다. - 새삼 자료구조 때 배운 내용 복기

아님 그냥 벡터를 쓰고, 요소를 굳이 안지우고 start, end 등의 범위 인덱스 변수를 사용해도 된다. 뒤집힌 상태로 삭제하면 start를 한 칸 움직이고, is_reverse가 false면 안뒤집혀있으니 end를 한 칸 당기고 이런식으로. 투포인터처럼? 근데 그냥 디큐 쓰는 게 깔끔하다. 맨 위에 첨부한 정답 코드가 디큐 사용한 버전이다. 실제로 시간이 기존에 벡터보다 700ms에서 32ms로 줄었다. 굿.

 

 

아 디큐 쓰다가 또 깜빡한건데, for반복문으로 완전탐색할 때, size()변수 함부로 쓰면 안된다. pop하면서 자료구조의 size가 변동되니까 반복 덜 돌았는데 막 종료되고 그래버린다. 기초적인 내용인데 벡터처럼 습관적으로 size 쓰다가 바부같은 실수가 나오는 포인트...ㅎ back()로 값 취한 뒤에 pop 해주는 것도 잊지말기.

// 최종 배열 담기
    if(is_reverse) {
         while (!dq.empty()) {
            ans+= to_string(dq.back());
            dq.pop_back();
            if(dq.empty()) {
                break;
            }
            ans += ',';
        }
    } else {
         while (!dq.empty()) {
            ans+= to_string(dq.front());
            dq.pop_front();
            if(dq.empty()) {
                break;
            }
            ans += ',';
        }
    }

 

 

---

 

 

공부하기 싫으니 ps가 넘 재밋구 .. 컴네 공부하기 실탓 구현문제나 풀고싶다 ㅎㅎ..