백준 1406번 : 에디터(Java)

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

1406번: 에디터

---

[풀이]

 

•  먼저! 아직 못풀었습니다..ㅠ 문제 풀이를 두가지로 풀어봤는데 시간초과로 틀렸습니다.. 그래서! 일단 다른 블로그 참고를 해서 다시 한번 풀어볼려고 실패한 사례만 남기겠습니다.
•  문제는 자료구조를 이용하는 유형입니다.
•  처음에는 StringBuffer를 이용해서 풀었습니다. deleteCharAt() 메소드와 insert() 메소드를 이용해서 index를 옮기며 풀어봤는데 60%를 조금 넘기면 시간초과가 발생했습니다...

• 그래서, 이번에는 링크드리스트를 이용해서 문제를 풀었습니다. Character형의 링크드리스트를 선언해서 remove()메소드와 add() 메소드를 사용했는데 이번에는 10%가 넘어가니 바로 시간초과가...

•  결국, 다른 블로그를 참고해서 풀이를 확인했는데, 스택으로 구현한 분들이 대다수였습니다. 스택을 두가지 선언하여 커서를 왼쪽 커서와 오른쪽 커서로 분리해서 작성을 하는 것이었는데... 오호.. 그러한 부분을 저는 생각못했습니다. 
•  또 다른 풀이는 ListIterator을 이용한 풀이였습니다. Iterator을 상속한 인터페이스를 이용하는 것인데 이것도.. 생각을 못했습니다..
•  이번 문제로 일단 제가 각 자료구조에 대한 시간복잡도에 대한 생각이 부족했다는 것을 알게되었습니다. 이 부분 다시 한번 공부하고 풀어서 코드 올리도록 하겠습니다!!!