210326 개발일지(109일차) - 알고리즘 문제풀이(feat. stack) 백준 1406번
문제는 아래와 같다.
아래 코드로 처음 작성했는데, 시간초과가 났다.
import sys
array=list(sys.stdin.readline().rstrip())
n=int(sys.stdin.readline().rstrip())
commands=[sys.stdin.readline().rstrip().split() for _ in range(n)]
index=len(array)
for command in commands :
if command[0] == 'P':
array.insert(index, command[1])
index += 1
elif command[0] == 'L':
if index > 0 :
index -= 1
elif command[0] == 'D':
if index < len(array) :
index += 1
elif command[0] == 'B':
if index > 0 :
del array[index-1]
index -= 1
print(''.join(array))
시간복잡도를 O(n)보다 더 줄여야하는 문제였다. 해결 방법은 아래와 같이 생각하면 된다.
이렇게 생각하고, 아래와 같이 코드를 작성해서 완료했다.
import sys
array1=list(sys.stdin.readline().rstrip())
n=int(sys.stdin.readline().rstrip())
commands=[sys.stdin.readline().rstrip().split() for _ in range(n)]
array2=[]
for command in commands :
if command[0] == 'P':
array1.append(command[1])
elif command[0] == 'L' and array1:
array2.append(array1.pop())
elif command[0] == 'D' and array2:
array1.append(array2.pop())
elif command[0] == 'B' and array1:
array1.pop()
print(''.join(array1 + list(reversed(array2))))
Author And Source
이 문제에 관하여(210326 개발일지(109일차) - 알고리즘 문제풀이(feat. stack) 백준 1406번), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gojaegaebal/210326-개발일지109일차-알고리즘-문제풀이feat.-stack-백준-1406번저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)