[BOJ] 1406. 에디터

Jimeaning·2023년 4월 6일

스택

코딩테스트

목록 보기

60/143

Python3

문제

입출력

입출력 예시

시도

시간 초과가 나지 않도록 하는 것이 중요한 문제였다.

cursor라는 변수를 만들어 cursor의 위치를 저장하고, insert와 remove 함수를 사용했는데 시간 초과 에러가 났다.

에러 코드

import sys

s = list(input())
m = int(input())
cur = len(s)

for i in range(m):
    mth = sys.stdin.readline().split()
    
    if mth[0] == 'L' and cur > 0:
        cur -= 1
    elif mth[0] == 'D' and cur < len(s):
        cur += 1
    elif mth[0] == 'B' and cur > 0:
        s.remove(s[cur-1])
        cur -= 1
    elif mth[0] == 'P':
        s.insert(cur, mth[1])
        cur += 1
        
for i in s:
    print(i, end='')

st = list(input())
m = int(input())

cur = len(st)

for i in range(m) :
    mth = list(map(str, input().split()))
    
    if mth[0] == 'P' :
        st.insert(cur, mth[1])
        cur += 1
    elif mth[0] == 'L' :
        if cur > 0 :
            cur -= 1
    elif mth[0] == 'D' :
        if cur < len(st) :
            cur += 1
    elif mth[0] == 'B' :
        if cur > 0 :
            st.remove(st[cur-1])

print(''.join(st))

주요 포인트

스택 두 개를 만들어 값을 추가/삭제하는 연산과 커서를 이동하는 연산 모두 append와 pop을 사용한다. 이렇게 하면 O(1) 시간을 보장한다.

스택 왼쪽을 나타내는 st_l 변수에 문자를 입력 받는다.
스택 오른쪽을 나타내는 st_r 변수에 빈 리스트를 초기화한다.

for 문
1. 만약 mth[0]이 'L'이고, st_l이 True(값이 있으면)면,
st_l의 마지막 값을 pop해서 st_r 마지막 자리에 append해서 넣는다.
2. 만약 mth[0]이 'D'이고, st_r이 True(값이 있으면)면,
st_r의 마지막 값을 pop해서 st_l 마지막 자리에 append해서 넣는다.
3. 만약 mth[0]이 'B'이고, st_l이 True(값이 있으면)면,
st_l의 마지막 값을 pop한다.
4. 만약 mth[0]이 'P'이면,
st_l의 마지막 값에 입력받은 mth[1]을 append 한다.

최종 출력
st_l와 st_r을 합쳐야 한다.
st_r를 reversed()로 반대로 돌린다. 이렇게만 하면 revered의 객체가 표현된다. 그래서 list로 형변환을 해준다.
"".join()은 fomat형식을 맞춰준다.
출력 예제처럼 나타낼 수 있게 된다.
ex) yxabc

이때 주의할 점은 st_r.reverse() 가 아닌 reversed(st_r) 를 사용해야 한다.
만약 모든 명령이 끝난 후 st_r에 값이 아무것도 존재하지 않는다면 st_r.reverse() 는 TypeError를 띄우기 때문이다.
반면에 reversed(st_r) 는 st_r에 값이 존재하지 않더라도 오류를 띄우지 않고 잘 작동한다.

최종 코드

import sys

st_l = list(input())
m = int(input())
st_r = []

for i in range(m):
    mth = sys.stdin.readline().split()
    
    if mth[0] == 'L' and st_l:
        st_r.append(st_l.pop())
    elif mth[0] == 'D' and st_r:
        st_l.append(st_r.pop())
    elif mth[0] == 'B' and st_l:
        st_l.pop()
    elif mth[0] == 'P':
        st_l.append(mth[1])
        
print(''.join(st_l+list(reversed(st_r))))