5430.AC

이번에 풀어볼 문제는 백준의 5430번 AC이다. 

난이도가 많이 어렵기보단 센스가 필요한 거 같다. 문제를 보도록 하자.

.....??????

 

 

5430번: AC

 

 

< Code 설명 >

#include <iostream>
#include <deque>
#include <cstring>

using namespace std;


int main() {
    int t;
    cin >> t;

    string p;        // 명령어를 받을 문자열
    deque<char>cmd;  // 명령어가 저장됨
    deque<int>arr;   // 숫자 배열이 저장됨

    for(int i=0; i<t; i++){
        char str_arr[400005]; // 숫자를 저장할 배열
        memset(str_arr,0,400005); // 초기화
        cin >> p;                 // 명령어를 입력받음
        int cnt_D =0;             // 'D'가 몇 개나오나 확인
        for(int j=0; j<p.length(); j++){
            if(p[j]=='D') // 'D'가 있을 때마다 확인함
                cnt_D++;  // 있으면 ++ 
            if(!cmd.empty() && cmd.back()==p[j] && cmd.back()=='R'){
                cmd.pop_back(); // 스택이 비지 않았을 때 제일뒤와 비교값이 'R'로 같으면
                             // pop해준다. 그 이유는 두 번 뒤집으면 안하는 것과 같으니까
            }
            else
                cmd.push_back(p[j]); // 위의 조건과 상관없다면 push!
        }
        // -> 새로운 명령어가 탄생함 ex)RRRRD -> D, RRRD -> RD
        // cmd deque에 저장
        
        int n=0;
        cin >> n >> str_arr; // 숫자의 길이와 숫자값을 입력받는다.
        char * tmp = strtok(str_arr, "[,]"); 
        while(tmp) {
            arr.push_back(stoi(tmp));
            tmp = strtok(NULL, "[,]");
        }

        int cmd_len = cmd.size(); // 명령어 길이를 저장

        int er_chk=false;         // 가능한지 불가능한지 체크
        if(arr.size()<cnt_D)      // D의 갯수보다 숫자 길이가 짧으면
            er_chk=true;          // error이므로 true 변경

        bool check=false;         // 뒤집혀서 가는지 안가는지 확인하는 변수
        for(int z=0; z < cmd_len; z++){ // 명령어 길이 만큼 
            if(cmd.front()=='R'){ // 명령어 제일 앞이 'R'이면 
                if(check==true){  // 현재 뒤집힌상태로 진행중이라면
                    check=false;  // 다시 R이 나왔으므로 원상복구 
                    if(!cmd.empty()) // 명령어 스택이 안비었다면
                        cmd.pop_front(); // 사용한 명령어 제거
                    continue; // true일 경우 아래 진행할 필요 없으므로 continue;
                }
                check=true;       // 처음 'R'을 만났으니까 뒤집힘 표시 'true'
                if(!cmd.empty())  // 명령어 deque가 안비었다면
                    cmd.pop_front(); // 사용한 명령어 제거
            }
            else if(cmd.front()=='D' && check==true){ // 뒤집힌 상태일때
                if(!cmd.empty())
                    cmd.pop_front();
                if(!arr.empty())
                    arr.pop_back();
            }
            else if(cmd.front()=='D' && check==false){ // 정방향일경우
                if(!cmd.empty())
                    cmd.pop_front();
                if(!arr.empty())
                    arr.pop_front();
            }
        }
        int len = arr.size();
        if(er_chk){ // 'D'의 갯수가 숫자 갯수보다 많을 경우 에러!
            cout << "error\n"; // 에러출력
        }else{
            cout <<"[";  // 아닌 경우 동작이 완료된 내용 출력
            if(check==true){ // 뒤집힌 상태로 출력
                for(int f=0; f<len; f++){
                    cout << arr.back();
                    arr.pop_back();
                    if(f!=len-1)
                        cout <<",";
                }
            }
            else{ // 정방향 출력
                for(int f=0; f<len; f++){
                    cout << arr.front();
                    arr.pop_front();
                    if(f!=len-1)
                        cout <<",";
                }
            }
            cout <<"]\n";
        }
        arr.clear();
    }
    return 0;
}

반드시 알아야 할 TIP!!

# 이번 문제 역시 입력받는 부분에서 고생했다 -> 이 부분 해결이 필요하다.

# 그리고 문제를 잘 읽어야한다. 이번 문제에서 또하나 실수한 점은 입력받는 숫자가 세 자리까지도 가능하다는 것이었다. 

 

 

# 이번 문제는 겉으로보긴 쉬워보이지만 문제 그대로 뒤집겠다고 reverse를 구현하면 틀리게된다.

-> 그 이유는 너무 많은 양의 계산이 소모되기 때문이다. 배열을 뒤집으려고 옮기고 하는게 시간초과를 일으켰다.

-> 이 문제의 아이디어는 뒤집었다고 생각하게 만드는 것이다. 굳이 뒤집을 필요없이 계산 시작 위치를 바꿔주는 것이다.

-> 즉, 위치를 뒤집었다고 생각하고 계산하도록 구현하면된다.