9935번 - 문자열 폭발
bomb의 끝 문자("ABCDE"에서 'E')를 bomb이 완성되는 트리거로 생각해서 트리거를 만나면 bomb의 길이만큼 slicing, 해당 부분 문자열이 bomb과 같으면 소멸문자열 길이 = N, 폭탄 길이 = M이라고 했을 때 시간 복잡도는 O(N*M) (Max 36_000_000)equals를 M-1만큼 하고('E'를 넣기 전 "ABCD"와 비교) append를 반복 뒤에 하는게 성능 상으로는 더 좋을듯 싶네요
이것도 넓게 보면 스택의 일종으로 생각해도 좋을 것 같습니다.
스택이라는 것이 결국 마지막에 넣은 것을 처음으로 빼낸다는 개념인데, 문자열의 마지막이 일치하면 -> 마지막에 넣은 것들을 확인하는 구조니까요.
댓글을 작성하려면 로그인해야 합니다.
xogus4020112 1년 전
bomb의 끝 문자("ABCDE"에서 'E')를 bomb이 완성되는 트리거로 생각해서
트리거를 만나면 bomb의 길이만큼 slicing, 해당 부분 문자열이 bomb과 같으면 소멸
문자열 길이 = N, 폭탄 길이 = M이라고 했을 때 시간 복잡도는 O(N*M) (Max 36_000_000)
equals를 M-1만큼 하고('E'를 넣기 전 "ABCD"와 비교) append를 반복 뒤에 하는게 성능 상으로는 더 좋을듯 싶네요