[백준/C++]#1406 - 에디터

풀이

#include <cstdio>
#include <cstring>
#include <stack>

using namespace std;
char a[600000];
int main() {
    scanf("%s", a);				// 문자열 입력받는다.
    stack<char> left, right;
    int m = strlen(a);			// 문자열의 길이
    for (int i=0; i<m; i++) {	// left 스택에 각 문자를 넣어줌.
        left.push(a[i]);
    }
    int n;
    scanf("%d", &n);			// 명령의 개수 입력
    while(n--) {
        char com;				// 각 명령 입력
        scanf(" %c", &com);
        if (com == 'L') {
            if (!left.empty()) {		// 'L'이면서 left 스택이 비지 않았을 때
                right.push(left.top());
                left.pop(); 
            }
        } else if (com == 'D') {		// 'D'이면서 right 스택이 비지 않았을 때
              if (!right.empty()) {
              left.push(right.top());
              right.pop();
            }
        } else if (com == 'B') {		// 'B'이면서 left 스택이 비지 않았을 때
              if (!left.empty()) {
              left.pop();
            }
        } else if (com == 'P') {		// 'P'일 때 left 스택에 값 입력 받음
              scanf(" %c", &com);
              left.push(com);
        }
      }
      while (!left.empty()) {			// left에서 right로 스택 성분 이동
        right.push(left.top());
        left.pop();
    }
    while (!right.empty()) {			// right에서 문자 출력하고 pop()
        printf("%c",right.top());
        right.pop();
    }
	return 0;
}

C++ 개념

이번에는 C++에서 C언어의 라이브러리를 사용한다. <cstdio>를 통해 scanf, printf를 사용하며, <cstring>을 통해 strlen() 함수를 사용한다. C++에서 <string> 라이브러리를 사용해 string으로 문자열을 받지 않는 이유는 계산속도 때문이다. 또한 <iostream>의 cin과 cout도 속도가 느리므로 대체되었다.

 

---

풀이

에디터 기능은 커서를 기준으로 문자열의 변경이 이뤄진다. 하나의 문자열을 사용해 계산을 진행하면 특정 성분(커서 앞,뒤)으로 접근하는데 O(n)의 계산이 필요하고 n번의 시행이 진행되므로 O(n^2)의 시간복잡도를 가진다.

문제에서는 0.3초의 시간제한이 존재하는데, 명령어의 최대입력 M의 500,000의 제곱은 이를 아득히 넘어서는 시간이 걸린다. 따라서 O(n) 시간복잡도의 문제로 만들어야하는데, 이때 쓰이는 것이 스택이다.

두 개의 스택을 사용해 커서의 앞, 뒤를 나누면 특정 성분으로 접근하는데 O(1)의 계산밖에 필요하지 않다.

 

초기 문자열을 입력받고, 명령의 개수를 입력받는다.

이제 반복문안에서 각 명령을 if 조건문으로 받아, 각 case에 대한 처리를 해주면 된다.

switch 조건문을 사용해 식을 간단히 만들려고 했으나, 인자로 문자를 받지 못하기 때문에 사용하지 못했다.

 

'L','D','B'의 경우 기존 스택이 비어있으면 실행되지 않으므로, if문 안에서 한번더 if문을 구현해야한다.

그리고 이는 C++의 STL의 특이한 점같은데, stack 함수 중 pop()은 값을 반환을 하지 않는다.

따라서 값을 이동하려면 top()을 사용해 값을 입력받은 이후 pop()을 사용해야한다.

모든 명령이 끝나면, 첫번째 스택의 값을 두번째 스택에 넣고, 두번째 스택에서 값을 반환한다.

---

+a

엄청 많은 시행착오가 있었다. 시간초과가 안되게 만드는 것이 정말 힘들었다.

몇가지 헤매었던 점을 정리해보면

 

①strlen(a);

식을 간단히 하고 싶어서 strlen(a)를 for문에 넣고 사용하니 시간초과가 발생했다.

반복 될 때마다 strlen(a)의 계산이 실행되는 것은 큰 부담이 되는 것 같다.

 

②scanf(" %", &com);

C언어를 잘 쓰지 않는 이유라고 생각된다. P $의 입력 때문에 입력 형식에 맞게 한 칸 띄워서 값을 입력받아야한다.

P $입력에 한해 "%"로 입력하면 띄어쓰기를 인식하는지, 올바르게 if문을 통과하지 못한다.

 

③마지막 출력에 문자열 사용

초기 정의한 a 문자열을 재활용하고 싶어서, for문을 써서 그대로 입력받았더니, 시간초과도 그렇지만 이전에 a 문자열에 대입된 값이 유지되어 출력되는 문제가 있었다. 초기화을 하려했으나 컴파일에 오류가 발생한다.

따라서 새로 b 문자열을 만들어서 입력받으니, 이 또한 시간초과의 문제가 발생했다.

 

문제에 접근하는 것은 어렵지 않으나, 시간초과가 발생하지 않게 하는 것은 어려웠다!