백준 1406 - 에디터

백준 1406 - 에디터

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

풀이

시간 제한이 매우 짧게 주어진 문제임을 확인하고 풀이에 들어가야 한다.

최대 600,000 글자까지 입력 가능하여 N 제곱의 시간으로는 풀지 못한다.

따라서 연결 리스트를 문제에 활용해야 하며, C++ STL의 list를 이용하였다.

문제의 조건에 맞게 코딩하면 되지만, list STL 에서 erase 함수와

insert 함수의 수행 시 iterator가 어느 위치를 가리키는지를 정확히 알아야 한다.

참고로 C++ STL list 에서는 더미 노드가 제일 뒤를 가리킨다.

C++ STL list

1. insert(iter, c) : ‘c’ 를 iter의 왼쪽에 삽입하고, iter는 원래의 값을 가리킴
2. erase(iter) : iter 위치의 값을 삭제하고, iter를 반환한다. 즉, 반환되는 iter 값을 받아 iter를 갱신해주어야 한다. (iter = list.erase(iter))

코드