JArchive 프로그래밍 일기

에디터 백준 1406번

리뷰

스택 2개를 이용해 풀었다.

커서를 기준으로 왼쪽에 있는 문자들은 왼쪽 스택에, 오른쪽에 있는 문자들은 오른쪽 스택에 넣는다.

커서를 기준으로 문자를 삭제하거나 삽입하거나 하기 때문에 stack을 활용할 수 있었다.

커서를 오른쪽으로 옮기는 연산은, 왼쪽 스택의 top을 오른쪽 스택에 push 하는 것이다.

커서를 왼쪽으로 옮기는 연산은, 오른쪽 스택의 top을 왼쪽 스택에 push 하는 것이다.

문제 해결 과정 

처음에는 런타임 에러가 났다. 고치다가 안되니까 1406번 문제 질문 게시판을 찾아봤다.

stack에서 pop 하기 전에 empty() 함수로 스택이 비었는지를 확인했어야 했다. 도움된 글

empty() 조건을 추가했더니, 이번에는 시간 초과가 났다.

이유는 결과 출력을 할 때, 스택에서 꺼낸 문자들을 string에 이어붙여가면서 했기 때문이었다.

왼쪽 스택에 있던 문자를 전부 오른쪽 스택으로 옮기고.

오른쪽 스택을 top 부터 빌때까지 전부 출력하면 시간 초과가 나지 않고 맞출 수 있었다.

코드

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main(void){

    stack<char> st_L, st_R; // 커서 기준으로 왼쪽 스택, 오른쪽 스택. 
    int M;
    string answer;

    cin >> answer >> M; // 초기 문자열과 명령어 횟수 입력받기 

    // 초기에 주어진 문자열을 전부 왼쪽 스택에 넣는다.  
    for(int i = 0; i < answer.size(); i++){
        st_L.push(answer[i]);
    }

    while(M--){ // 명령어 횟수 만큼 수행 

        char order, ch;
        cin >> order; // 명령어 입력받기 

        if(!st_L.empty() && (order == 'L') ){ // 왼쪽 스택의 top을 오른쪽 스택에 push

            ch = st_L.top();
            st_R.push(ch);
            st_L.pop();

        }else if(!st_R.empty() && (order == 'D') ){ // 오른쪽 스택의 top을 왼쪽 스택에 push

            ch = st_R.top();
            st_L.push(ch);
            st_R.pop();

        }else if(!st_L.empty() && (order == 'B') ){ // 왼쪽 스택을 pop 하면 top을 삭제한 셈.

            st_L.pop();

        }else if(order == 'P'){ // 문자를 받아서 왼쪽에 삽입

            cin >> ch;
            st_L.push(ch);
        }        
    }

    // 문자열을 처음부터 출력하기 위해, 
    // 왼쪽에 있는 문자들을 전부 오른쪽 스택으로 옮기기.
    while(!st_L.empty()){
        st_R.push(st_L.top());
        st_L.pop();
    }

    while(!st_R.empty()){ // 최종 출력 
        cout << st_R.top();
        st_R.pop();
    }
    return 0;
}