[Python][백준/BOJ] 1063번 : 에디터

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

1406번: 에디터

 

내 코드

 

 

리뷰

시간 복잡도

해당 문제는 문자열의 최대 길이가 100,000이고, 명령어의 최대 개수는 500,000이다.

만약 insert 와 remove 함수를 쓴다면, 최악의 경우에는 100,000 * 500,000 의 연산을 진행해야 한다.

insert 와 remove 함수의 시간 복잡도는 O(n)이 되기 때문이다.

그래서 답은 맞았는데도 불구하고 시간 초과가 자꾸 발생해서 통과할 수 없었다.

구글링을 해보니 사람들이 스택 2개를 사용해서 해결하는 것을 볼 수 있었다.

 

st.reverse() , reversed(st)

reverse() 에 아무 값도 없는 list가 들어간다면 TypeError가 발생한다.

하지만 reversed()에 값이 없는 list가 들어가더라도 에러는 발생하지 않는다.