xogus4020112   1년 전

bomb의 끝 문자("ABCDE"에서 'E')를 bomb이 완성되는 트리거로 생각해서

트리거를 만나면 bomb의 길이만큼 slicing, 해당 부분 문자열이 bomb과 같으면 소멸

문자열 길이 = N, 폭탄 길이 = M이라고 했을 때 시간 복잡도는 O(N*M) (Max 36_000_000)

equals를 M-1만큼 하고('E'를 넣기 전 "ABCD"와 비교) append를 반복 뒤에 하는게 성능 상으로는 더 좋을듯 싶네요

azruine   1년 전

이것도 넓게 보면 스택의 일종으로 생각해도 좋을 것 같습니다.

스택이라는 것이 결국 마지막에 넣은 것을 처음으로 빼낸다는 개념인데, 문자열의 마지막이 일치하면 -> 마지막에 넣은 것들을 확인하는 구조니까요.

댓글을 작성하려면 로그인해야 합니다.