dolpang2   9달 전

안녕하세요.

9935번 문제에서 질문 드립니다.

Naive 하게 생각했을 때 Python에서 제공하는 replace로 접근하면 될 것 같았는데

시간 초과가 나버리네요.

문제 분류를 보니 스택과 문자열 처리라고 하는데

알아야 하는 알고리즘이 따로 있나요?

그게 아니라면 어떤 식으로 접근하는지 힌트를 주시면 감사하겠습니다.

yukariko   9달 전

replace 하는 방법이 시간초과가 나는 이유는

여러번의 문자열 이동으로 인한것이라고 생각됩니다.

aabcbc 에서 abc를 지우는 경우

a(abc)bc 의 괄호친 abc를 지울때 뒤에있는 bc를 앞으로 당겨오는 연산이 들어갈탠데, 이부분이 느릴 수 있습니다.

제가 푼 방법을 말씀드리자면

abc를 지울때 지운다음 합치지말고, 지웠다는 표시만 하는것입니다. 

a___bc 같은 상태로 둔 다음 a 다음의 _를 만나면 실제 문자가 있는 b, c로 점프시키게 하는것으로 이동 시간을 줄였습니다.

dolpang2   9달 전

yukariko

감사합니다! 해당 아이디어로 다시 접근해보겠습니다.

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