ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 5430.AC
    알고리즘/백준 BAEK JOON 2020. 4. 13. 18:10

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

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

    .....??????

     

     

     

    5430번: AC

    문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.

    www.acmicpc.net

     

     

    < 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를 구현하면 틀리게된다.

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

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

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

    반응형

    '알고리즘 > 백준 BAEK JOON' 카테고리의 다른 글

    1793.타일링  (0) 2020.04.20
    1722.순열의 순서  (0) 2020.04.15
    1021.회전하는 큐  (0) 2020.04.09
    1966.프린터 큐  (0) 2020.04.07
    11866.요세푸스 문제 0  (0) 2020.04.06

    댓글

Designed by Tistory.