강의

멘토링

커뮤니티

인프런 커뮤니티 질문&답변

박완섭님의 프로필 이미지
박완섭

작성한 질문수

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

9935 문자열 폭발 질문입니다!

작성

·

286

0

안녕하세요 큰돌님.

 

http://boj.kr/c74689fce15941e8b098f94fda2f2d36

이렇게 제출을 하고 시간초과 판정을 받았는데요,

제 생각엔 문자열을 substr로 검사할 때도 인덱스를 결국엔 다 돌아야 돼서 문자열로 처리하는거랑 스택을 써서 보관하는 거나 시간복잡도 차이가 없을거라 생각했는데,

 

시간초과가 난 이유를 알 수 있을까요?

답변 1

0

큰돌님의 프로필 이미지
큰돌
지식공유자

안녕하세요 완섭님 ㅎㅎ

근데 이 코드 너무 비효율적인데 한번 이렇게 수정해보시겠어요?

지금 코드의 로직을 보면..

마지막 문자 >> 전체확인 >> 사이즈확인 >> 같지 않다면 제거 이렇게 되어있죠?

 

이거를.

먼저

c를 a stack에 넣고 >> a stack 사이즈와 p 사이즈 확인 아니라면 그냥 a stack에 넣기만.

사이즈 같다면.. 로직 진행.. 이런식으로 하는게 낫지 않을까요?

마지막 문자로 하시는 아이디어는 너무 좋습니다.

다만, 사이즈를 체크하지 않고 마지막 문자를 기반으로 하게 되면 사이즈 로직에 관한 처리가 계속해서 발생할 수 있을 것같고 그 부분이 불필요할 것같아서요.

이렇게 해서 다시 질문 주세요. ㅎㅎ 그걸로 봐드릴게요.

 

박완섭님의 프로필 이미지
박완섭

작성한 질문수

질문하기