에디터

문제

처음 풀이

단순히 list의 기능 중 pop과 insert를 이용해서 풀었다.
하지만 pop, insert를 하게 될 경우 O(n)이라는 시간복잡도 때문에 시간초과가 발생하였다.

풀이

https://corin-e.tistory.com/entry/%EB%B0%B1%EC%A4%80-1406-%EC%97%90%EB%94%94%ED%84%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC
위에 블로그를 통해 알게 되었다.

처음 풀이 했을 때에는 cursor_idx를 직접 움직였는데
해당 풀이는 cursor_idx기준으로 left, right 리스트를 두자

만약 P라는 명령어가 들어오면 "$"원소를 커서 왼쪽에 추가하자

만약 "L"라는 명령어가 들어오면 커서를 왼쪽으로 한 칸 옮겨야 한다.
이 커서를 직접 옮길 필요 없다.
그냥 left 리스트에서 마지막 원소를 pop해서 right 리스트에 append해주면 커서를 옮긴 것과 같은 효과가 나타난다.

하지만 right리스트는 뒤집혀 있다. 그래서 deque를 해서 appendleft하는 것도 방법이다.

만약 "D"명령어가 들어오면 right리스트의 마지막 원소를 pop해서 left 리스트에 append해준다.

이런식으로 하면 O(1)이라는 시간복잡도를 가질 수 있게 된다.
진짜 감탄이 나오는 풀인 것 같다.