안녕하세요. 늘 많은 도움 받고 있는데, 또 도움을 요청하려 이렇게 올리네요.

나름 속도를 위해서,  prev_idx, next_idx 배열을 둬서, 폭발이 일어난 직후, 폭발문자를 제외하고

앞뒤를 링크드 리스트 형식으로 연결하였습니다.

이후, 최종 출력은 next_idx 만 추적하여 출력하였는데, 저지서버에서 정답이 안뜨네요 : (

혹시, 출력문에서 시간이 많이 걸리는건 아닌가 해서

cout -> printf -> 모아서 한번에 버퍼로 담아두고 printf 로 변경해봤지만...

달라지지 않네요.

고수님들의 의견 부탁드려요!


pl0892029   8달 전

스택으로 짜시면 쉽지 않을까요? 'ㅂ'

pl0892029 님. 답변 감사합니다 : )

제가 링크드 리스트 스타일이라고 표현했지만, 실제 동작은 스택의 그것과 상당히 유사합니다.

폭발물이 의심되는 첫 캐릭터는 이전의 인덱스를 저장하고 진행한후, 폭발물 처리가 끝나면 이전의 인덱스로 돌아옵니다.

이렇게 반복이 되어 가면, 흡사 스택 구조와 유사해 보이는데요.

혹시 말씀해주시는 부분이, 제가 설명 드린 부분과 어떻게 다른지 여쭤봐도 될까요?

pl0892029   8달 전

1. 링크드 리스트가 아닌 직접 스택으로 짜보시는걸 추천드리는 의도였습니다.
스택을 이용하게 되면, 현재 위치에서 몇번째 explosion 문자와 비교해야되는지를 O(1)만에 판단할 수 있습니다.
결과값 또한 스택에 있는 원소를 그대로 출력하면 되기 때문이지요.
구현도 쉽고, 가독성도 좋기 때문에 추천드립니다.

2. 현재 코드와 스택의 차이점
do_something() 함수의 현재 동작은 O(LK) (L : 폭발 전 문자열, K : 폭발하는 길이 문자열)로 보입니다.
스택은 이 부분이 O(L)로 변경됩니다. 성능 상에서도 이점이 많아지지요.

+ 아래 코드처럼, 메모리를 많이 잡아먹는 변수는 전역 변수로 빼시거나 동적 할당을 추천드립니다.

앗!! 친절한 설명 감사드립니다~  큰 도움이 되었습니다. (ㅎ 깜빡하고 늦게 댓글 다네요 ㅠㅠ)

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