[백준] 에디터

출처:: www.acmicpc.net/problem/1406

분류:: 스택

 

1. 문제 이해 및 해결과정

- 두 개의 스택을 이용해서 풀 수 있으며 스택의 top이 커서가 된다. 투스택 - 스택1번이 커서 왼쪽 , 스택 2번이 커서 오른쪽이 된다  - 1. 스택 두개를 만든다. - 2. 초기 문자열을 스택1번에 넣는다 - L : 커서 왼쪽으로, 첫번째 스택의 top을 두번째 스택으로 push - B : 커서왼쪽의 문자삭제 , 첫번째 스택의 top을 pop - D : 커서를 오른쪽으로 , 두번재 스택의 top을 첫번재 스택으로 push  - P : 문자하나를 추가한다. => 스택1번에 append

 

 

2. 풀이방법

  1. 투 스택

#에디터
#https://www.acmicpc.net/problem/1406
import sys
sys.stdin = open("input.txt","r")
stackOne=list(sys.stdin.readline().rstrip()) #속도 높이기 위해서
stackTwo=[]
n=int(input()) #명령어 개수
for cmd in sys.stdin:
    if cmd[0] == 'L':
        if stackOne:
            stackTwo.append(stackOne.pop())
    elif cmd[0] == 'D':
        if stackTwo:
            stackOne.append(stackTwo.pop())
    elif cmd[0] == 'B':
        if stackOne:
            stackOne.pop()
    elif cmd[0] == 'P':
        stackOne.append(cmd[2])
print(''.join(stackOne+list(reversed(stackTwo))))

 

3. 오답원인

  1. 시간초과

시간초과가 났다 .... 이유를 찾아본 결과 리스트는 원소를 삽입하거나 삭제할때, 그 자리 이전,이후의 원소들을 한킨씩 밀거나 당기는 작업이 필요해서 시간이 오래걸린다 insert나 del은 시간복잡도가 O(n) => 즉, 파이썬 리스트 특성의 문제

이를 해결하기 위해서는 

   1) 리스트 맨 뒤에서만 삽입, 삭제가 가능하도록 하기

   2) 다른,,자료구조,,이용하기,,

#에디터 - 시간초과
#https://www.acmicpc.net/problem/1406
import sys
sys.stdin = open("input.txt","r")
#인덱스를 커서로 0 A 1 B 2 C 3 D
#L: 인덱스 -1 만약에 인덱스가 0이면 무시
#D : 인덱스를 +1 오른쪽으로 , 인덱스가 문자열 길이와 같다면 무시
#B : 인덱스에 있는 문자 삭제
#P X : 인덱스 i에 문자 추가
str=" "
str+=input()
str=list(str)
n=int(input()) #명렁어의 개수
leng=len(str)
cur=leng-1
for i in range(n):
    com=input()
    if com[0]=='L':
        if cur!=0:
            cur-=1
    elif com[0]=='D':
        if cur!=leng:
            cur+=1
    elif com[0]=='B':
        if cur!=0:
            del str[cur]
            cur -= 1
            leng-=1
    elif com[0]=='P':
        com=com.split()
        str.insert(cur+1,com[1])
        cur+=1
        leng+=1
print(''.join(str[1:]))

 

4. 알게된 점

두 개의 스택을 이용해서 문제푸는 방법

 

입력 자체로 데이터 활용하기

for cmd in sys.stdin:

두개를 join해서 출력하기

print(''.join(stackOne+list(reversed(stackTwo))))