[BOJ] 3111번: CENZURA

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


맨 처음에는 문자열폭발 문제(http://baaaaaaaaaaaaaaaaaaaaaaarkingdog.tistory.com/103)와 거의 유사한 문제라고 생각을 했는데, 여기는 패턴의 문자가 서로 다르다는 조건이 없기 때문에 그 문제를 풀듯이 해결할 수가 없습니다. 그걸 깨달은게 어제 잠들기 직전이었고 패턴(A)의 길이가 25라는 점에서 착안, 그냥 linked list로 문자들을 엮어두고 앞 뒤에서 탐색하며 제거하는 식으로 해결하면 충분히 시간 내에 해결이 되겠다는 아이디어를 오늘 아침 떠올렸습니다.(KMP를 활용하면 O(TA) 대신 O(T+A)로 떨굴 수 있을 것 같습니다.)


그런데 정작 구현에서 엄청 애를 먹었습니다. 역순으로 탐색하는 부분은 reverse_iterator를 활용하려고 했는데, 제가 봤을땐 틀린게 없는데 제출하면 계속 런타임에러가 발생하고 어떤 경우에 런타임에러가 발생하는지도 찾지 못해서 소스를 그냥 갈아엎었습니다. 저녁 8시쯤부터 다 짜고나서 밥을 먹어야겠다고 생각했는데 2시간 반동안 붙들렸네요. 매우 배고픕니다.


https://github.com/blisstoner/BOJ/blob/master/3111.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 5052번: Phone List  (0) 2018.01.27
[BOJ] 4354번: Power Strings  (0) 2018.01.27
[BOJ] 1701번: Editor  (0) 2018.01.24
[BOJ] 3111번: CENZURA  (0) 2018.01.22
[BOJ] 14891번: 톱니바퀴  (0) 2018.01.21
[BOJ] 2841번: GITARA  (0) 2018.01.20
[BOJ] 3986번: 좋은 단어  (0) 2018.01.20
  Comments
댓글 쓰기