[알고리즘] 백준 알고리즘 1406 에디터

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 포스팅할 백준알고리즘 문제는 1406 에디터 문제인데요, 명령으로해서 문자열들을 처리할 수 있는지 여부를 알 수 있었던 문제였습니다. 그럼 풀이 들어갈게요! 

문제 링크 에디터 1406번문제

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

---

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

L	커서를 왼쪽으로 한 칸 옮김 (커서가 문장의 맨 앞이면 무시됨)
D	커서를 오른쪽으로 한 칸 옮김 (커서가 문장의 맨 뒤이면 무시됨)
B	커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) 삭제로 인해 커서는 한 칸 왼쪽으로 이동한 것처럼 나타나지만, 실제로 커서의 오른쪽에 있던 문자는 그대로임
P $	$라는 문자를 커서 왼쪽에 추가함

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

입력

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 N(1≤N≤500,000)이 주어진다. 셋째 줄부터 N개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

출력

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

예제 입력 1 

abcd
3
P x
L
P y

---

간단히 문제를 살펴볼까요? 이 문제를 풀기위해서는 문제에서 어떤점을 요구하는지를 잘 파악해야합니다.

1) 편집기에 입력에 있어서 최대 600,000글자 까지 입력이 가능한 조건

2) 'L' 커서를 왼쪽으로 한칸옮기는 명령어

3) 'D' 커서를 오른쪽으로 한칸옮기는 명령어

4) 'B' 커서 왼쪽에 있는 문자를 삭제함

5) 'P' $ 커서 왼쪽에 문자를 추가함

이라는 조건을 잘 파악해야할것입니다.

그리고 특히 이문제에 대해서는 어떻게 풀까라는 생각을 잘 해봐야할것인데요, 저는 STL의 Stack의 자료구조형을 사용하여 이문제를 풀어보겠습니다.

그이유는 커서 위치에 따라 왼쪽 문자열 / 오른쪽 문자열로 나누어 질 수 있는데, 커서 위치를 기준을 삼기위해서 저는 Stack을 2개를 생성하여 Left Stack , Right Stack을 생성하였습니다. 이것이 이 문제의 키 포인트라고 할 수 있습니다.

예를 들어보죠)

TestCase에서 나온 

abcd
3
P x
L
P y

를 간단하게 살펴보겠습니다.

- abcd의 문자열을 입력을 받습니다.

- 총 3개의 테스트 케이스(커멘트 명령어수를 입력을 받습니다)

- P명령어가 들어왔습니다. 단 , 맨처음에 입력으로 들어온 문자열들을 모두 왼쪽 stack에 집어 넣습니다.

- "P x"  x라는 문자열을 왼쪽 스택의 가장 top부분에 추가시켜줍니다. 현재 커서는 왼쪽 스택의 끝에 있습니다. 

- "L"명령어로 커서를 왼쪽으로 한칸이동 시켜줍니다. 이때 중요한것이 있습니다. 커서를 왼쪽으로 한칸이동해주기 위해서는 abcd + x 가 들어온 abcdx 가 현재 왼쪽 스택에 위치해어 있습니다. 커서를 한칸 옮기기 위해서는 어떻게 해야 할까요?

* 네 바로, 왼쪽 스택의 top부분을 오른쪽 스택의 맨위에 부분으로 push를 해주면 왼쪽 /오른쪽 스택을 기준으로 커서가 이동하는것을 확인할 수 있을것입니다.

- "P y" 의 명령어가 들어오고 왼쪽 스택의 top부분에 push를 해주면 

Testcase 1의 상황이 종료되게 됩니다.

이렇게 제가 말한것들을 바탕으로 

C++ 소스코드로 구현해보았습니다.

//

//  1406(에디터).cpp

//  Algorigm_Study

//

//  Created by kgh on 16/12/2018.

//  Copyright © 2018 kgh. All rights reserved.

//

#include <cstdio>

#include <cstring>

#include <stack>

using namespace std;

char ch[600000];

int main(void){

    // 길이가 600,000을 넘지 않는 문자열 입력

    scanf("%s",ch);

    // 명령 몇번 실행할지 여부

    

    // stack 2개를 사용하여 커서를 확인할것이기 때문에 left,right선언

    stack<char> left,right;

    int n = strlen(ch);

    // stack left에 값들 모두 넣어주기, right는 나중에 커서 위치확인하려고 사용할것임.

    for(int i=0; i<n; i++){

        left.push(ch[i]);

    }

    int num;

    scanf("%d",&num);

    // 몇번의 명령을 실행할것인지에 대한것

    while(num--){

        // 명령 입력

        char command;

        scanf(" %c",&command);

        

        // 'L'일경우 커서를 왼쪽으로 옮김 == 왼쪽 스택에 있는 top부분을 빼서 오른쪽 스택에 넣는다.

        if(command == 'L'){

            if(!left.empty()){

                right.push(left.top());

                left.pop();

            }

        }else if(command == 'D'){  // 'D'일경우 커서를 오른쪽으로 한칸 옮긴다.

            if(!right.empty()){

                left.push(right.top());

                right.pop();

            }

        }else if(command == 'B'){  // 'B'일경우 왼쪽에 있는 커서를 삭제한다. (top부분)

            if(!left.empty()){

                left.pop();

            }

        }else if(command == 'P'){ // 'P'입력시 $부분을 새로 입력받기 위함.

            char p_string;

            scanf(" %c",&p_string);

            left.push(p_string);

        }

    }

    // left stack에 있는값들을 모두 오른쪽으로 옮기고 stack 에서 pop해준다.

    while(!left.empty()){

        right.push(left.top());

        left.pop();

    }

    // left stack에서 값을 모두 옮겼으니까 stack top부분에 있는값들을 하나씩 출력해주면서 뺴준다.

    while(!right.empty()){

        printf("%c",right.top());

        right.pop();

    }

    printf("\n");

    return 0;}

이상 백준알고리즘 에디터 1406번 문제 풀이 및 코드리뷰를 마치겠습니다.

감자 코딩에 감자개발자였습니다 :) 감사합니다.