백준 1406번 어떻게 풀었나. 파이썬 내장함수 시간복잡도 정리

• 푼 방법
  • 처음엔 insert와 del을 사용하였다.
  • 그랬더니 시간초과가 나왔다.
  • 왜 그린지 못찾겠어서 구글링했다. 
  • insert와 del은 시간복잡도가 O(n)이다. 사용을 지양하는 것이 좋다.
  • 구글링을 한 결과, 스택을 두개 사용하여 풀 수 있었다.
• 고치면 좋을 부분
  • 파이썬의 내장함수의 시간복잡도를 잘 알아야 겠다.
  • 걸리는 시간을 고려하지 않고 작성했다.
  • 계획하기 단계를 좀 더 체계적으로 해야 될거 같다
  • .readline().strip() 보다 .readline().rstrip()이 더 빠를거 같다.
• 파이썬 내장함수 시간복잡도 정리
  
  • https://wayhome25.github.io/python/2017/06/14/time-complexity/

 

---

코드 

import sys

stackLeft = list(sys.stdin.readline().rstrip())
stackRight = list()

N = int(sys.stdin.readline())

for i in range(N):
	cmd = list(sys.stdin.readline().split())
	if cmd[0] == 'L' and stackLeft:
		stackRight.append(stackLeft.pop())
	elif cmd[0] == 'D' and stackRight:
		stackLeft.append(stackRight.pop())
	elif cmd[0] == 'B' and stackLeft:
		stackLeft.pop()
	elif cmd[0] == 'P':
		stackLeft.append(cmd[1])

print(''.join(stackLeft) + ''.join(list(reversed(stackRight))))

참고자료

https://developer-doreen.tistory.com/51?category=1133953 

https://developer-doreen.tistory.com/29

감사합니다