에디터 백준 1406 문제 풀이

문제풀이 핵심

쉬운 로직인 문제이지만 시간제한이 0.3초로 효율성이 중요한 문제였다. 문제를 그대로 로직으로 만들어 인덱스 삽입과 삭제를 했다면 시간초과를 맛볼 수 있는 문제이다 😂

최대한 삽입과 삭제를 하지 않는 방법을 생각해내야 했고 나는 stack을 이용하기로 결심했다. stack의 pop과 append만을 사용해서 인덱스를 고려하지 않고도 풀 수 있겠다고 생각했다.

두 개의 스택을 사용한다.

왼쪽 스택과 오른쪽 스택을 만든다. 처음 주어진 문자는 그대로 왼쪽 스택으로 들어간다. 그리고 명령어에 따라
L : 왼쪽스택에서 pop한 뒤 그 값을 오른쪽 스택에 append한다.
D : 오른쪽 스택에서 pop한 뒤 그 값을 왼쪽 스택에 append한다.

• 순서가 달라질까 걱정이 들지만 LIFO인 스택의 특성상 삽입 시 순서가 달라지지 않는다. 마지막에만 거꾸로 바꿔주면 된다. (추후설명)

B : 왼쪽스택에서 pop한다.(로직 그대로 짰으면 del list(index)를 사용) 매우 간단해짐을 알 수 있다.
P : 왼쪽스택에 append한다. (로직 그대로 짰으면 insert(index, 'str')을 사용)

오른쪽 스택은 문자열이 거꾸로 append되므로 마지막에 print 할때 reversed상태로 print해준다.

결론 : B, P 명령어에서 급격한 시간단축을 가져올 수 있다.

소스코드