[BEAKJOON] 백준 1406번 : 에디터

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

1406번: 에디터

 

시간제한이 0.3 초인 문제이다.

 

시간 초과된 나의 풀이

import sys
input = sys.stdin.readline

sentence = input()

index = len(sentence)-1

N = int(input())

while(N):
    N -= 1
    M = input()
    if(M[0]=='L'):
        if(index != 0):
            index -= 1
        #index -= 1 if index != 0 else index
    elif(M[0]=='D'):
        if(index != len(sentence)-1):
            index += 1
        #index += 1 if index != (len(sentence)-1) else index
    elif(M[0]=='B'):
        if index!=0:
            sentence = sentence[:index-1]+sentence[index:]
            index -= 1
    else:
        sentence = sentence[:index]+M[2]+sentence[index:]
        index += 1

print(sentence)

 

저기 중간에 주석 처리한 부분 삼항 연산자 시도를 해보려고 했는데, 'D' 부분에서 계속 올바른 값이 나오지 않는다.. 내가 파이썬의 삼항연상자를 잘 못 이해하고 있는 것인가..

 

처음에 중간에 값을 어떻게 넣어다 빼는 것을 생각하던 도중에 문자열 슬라이싱을 index를 두어서 하면 될거라고 생각을 했다. 그러나 시간 초과로 되지 않았다.

실제로 해당 문제는 시간초과가 0.3초로 일반적인 문제보다 훨씬 짧은 시간제한을 가지고 있다.

 

아래는 다른 사람의 코드를 보고 내 스타일대로 각색한것이다.

import sys
input = sys.stdin.readline

str_stack1 = list(input().rstrip())
str_stack2  = []

for _ in range(int(input())):
    M = input()
    if(M[0]=='L'):
        if(str_stack1):
            str_stack2.append(str_stack1.pop())
    elif(M[0]=='D'):
        if (str_stack2):
            str_stack1.append(str_stack2.pop())
    elif(M[0]=='B'):
        if(str_stack1):
            str_stack1.pop()
    else:
        str_stack1.append(M[2])

str_stack1.extend(reversed(str_stack2))
print(''.join(str_stack1))

자료 구조 활용에 아직 부족하다고 느꼈다.

 

접근법은, 커서를 기준으로 문자열을 스택 두개에 나누어 담겠다는 것이다.

 

값을 추가하거나 삭제하는 연산, 커서를 이동하는 연산 모두 append와 pop을 통해 할 수 있어 O(1) 시간의 연산을 보장한다.

반복문에서 명령을 모두 수행한 후, stack2를 뒤집어준 후 extend 함수를 활용해 두 stack을 합쳐주었다.

출력은 문자열로 해야하기 때문에 join함수를 활용한다.

 

마지막 str_stack2를 뒤집어주는 과정에서 str_stack2.reverse()를 한다면, 만일 str_stack2에 값이 존재하지 않는다면, str_stack2.reverse() 는 TypeError를 띄운다.
+ reversed(x)는 x 안에 값이 존재하지 않더라도 오류를 띄우지 않는다.