9935번 - 문자열 폭발
문자열을 처리하는 방식으로 진행하였고요.
for문 돌면서 폭발문이 있는지 확인한다음에 새로운 배열에 넣고
마지막으로 넘치는 부분만 삭제하도록 처리하였습니다.
for문을 한번만 처리하였고 마지막에만 추가 처리하도록 하였기때문에
O(n+m) 시간이 걸린다고 생각하고 있습니다.
근데 2%에서 시간 초과가 뜨네요...
예상을 해본다면 substring으로 자르는 부분인데 만약 저부분에서 그런다고 한다면... 어떻게 처리해야 되는지 감이 안오네요...
도와주시면 감사하겠습니다.
substring(j-boomStr.length(), j) 때문에 선형시간이 아닌 것 같네요.
매 루프마다 boomStr의 길이만큼 전부 볼 필요는 없습니다.
댓글을 작성하려면 로그인해야 합니다.
shfksekdrms2 6년 전
문자열을 처리하는 방식으로 진행하였고요.
for문 돌면서 폭발문이 있는지 확인한다음에 새로운 배열에 넣고
마지막으로 넘치는 부분만 삭제하도록 처리하였습니다.
for문을 한번만 처리하였고 마지막에만 추가 처리하도록 하였기때문에
O(n+m) 시간이 걸린다고 생각하고 있습니다.
근데 2%에서 시간 초과가 뜨네요...
예상을 해본다면 substring으로 자르는 부분인데 만약 저부분에서 그런다고 한다면... 어떻게 처리해야 되는지 감이 안오네요...
도와주시면 감사하겠습니다.