2018. 1. 22. 22:41, 알고리즘/BOJ
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시간 반동안 붙들렸네요. 매우 배고픕니다.
'알고리즘 > 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] 14891번: 톱니바퀴 (0) | 2018.01.21 |
[BOJ] 2841번: GITARA (0) | 2018.01.20 |
[BOJ] 3986번: 좋은 단어 (0) | 2018.01.20 |
Comments