JArchive 프로그래밍 일기

문제

에디터 1406

List 를 이용한 "맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
list<char> strList;
string str;
int M;
char ch, x;
​
void input(){
​
    cin >> str >> M; // 초기 문자열, 명령의 횟수
​
    // 문자열의 문자를 리스트에 넣는다.
    for(int i = 0; i < str.size(); i++){
        strList.push_back(str[i]);
    }
​
    auto cur = strList.end(); // 커서는 마지막을 가리키고 있다
​
    while(M--){ // 명령 수행
​
        cin >> ch;
​
        if(ch == 'P') {
            cin >> x;
            strList.insert(cur, x); // 문자를 커서 왼쪽에 추가
        }
        else if(ch == 'L') {
            if (cur != strList.begin()) { // 맨 처음이 아니면,
                cur--; // 커서를 왼쪽으로 한 칸 옮김
            }
        }
        else if(ch == 'D'){
            if(cur != strList.end()){ // 커서가 맨 마지막이 아니면,
                cur++; // 커서를 오른쪽으로 한 칸 옮김
            }
        }else { // 'B'
            if(cur != strList.begin()){ // 커서가 맨 마지막이 아니면,
                cur--; // 커서 기준 왼쪽이니까 -- 해준다.
                cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신
            }
        }
    }// while
​
    for(auto c : strList) cout << c;
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
}

Stack 을 이용한 "맞았습니다"코드

#include <bits/stdc++.h>
using namespace std;
​
stack<char> leftStack;
stack<char> rightStack;
string str;
int M;
char ch, x;
​
void input(){
​
    cin >> str >> M;
​
    for(int i = 0; i < str.size(); i++){
        leftStack.push(str[i]);
    }
​
    while(M--){ // 명령 횟수만큼 반복 
​
        cin >> ch; // 명령 문자 
​
        switch(ch){
            case 'P':
                cin >> x; // 추가할 문자 
                leftStack.push(x); // 문자를 커서 왼쪽에 추가
                break;
            case 'L':
                if(!leftStack.empty()){ // 왼쪽 스택에 문자가 있는지 확인 
                    rightStack.push(leftStack.top());  // 왼쪽 스택에 있던 top을 오른쪽 스택에 넣는다 
                    leftStack.pop(); // 실제 pop()연산 수행 
                }
                break;
            case 'D':
                if(!rightStack.empty()){ // 커서 오른쪽에 문자가 있는지 확인 
                    leftStack.push(rightStack.top());
                    rightStack.pop();
                }
                break;
            case 'B':
                if(!leftStack.empty()){
                    leftStack.pop();
                }
                break;
        }// switch
    }// while
​
    while(!leftStack.empty()){ // 문자를 순서대로 꺼내야 하니까. 왼쪽스택에 있던것을 오른쪽으로 전부 이동시킴
        rightStack.push(leftStack.top());
        leftStack.pop();
    }
​
    while(!rightStack.empty()){ // 실제 답 출력 
        cout << rightStack.top();
        rightStack.pop();
    }
}
​
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.ignore(0);
​
    input();
    return 0;
}

연결리스트를 이용한 경우 리뷰

커서의 위치를 저장하기 위해 iterator를 이용했다.

auto cur = strList.end(); // 커서는 마지막을 가리키고 있다

erase 함수로 커서가 가리키는 문자를 삭제하고 나서, 커서의 주소를 갱신해주는 것을 유의해야 한다.

cur = strList.erase(cur); // 문자 삭제 후, 주소값을 갱신

스택을 이용한 경우 리뷰

커서를 기준으로 두고 스택을 2개 사용했다.

커서를 기준으로 왼쪽에 저장할 문자를 담을 스택, 커서를 기준으로 오른쪽에 저장할 문자를 담을 스택.

4가지 연산 모두 커서 위치를 기준으로 발생하기 때문이다.

에디터 백준 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;
}