dolpang2   10달 전

안녕하세요.

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

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

시간 초과가 나버리네요.

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

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

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

yukariko   10달 전

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

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

aabcbc 에서 abc를 지우는 경우

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

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

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

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

dolpang2   10달 전

yukariko

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

minqw5   3주 전

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

밑줄 친 부분을 어떻게 구현해야될까요???           _ 때문에 abc로 인식이 안되는데 점프를 해서 어떻게 abc로 인식이 되게끔 하신건지 궁금합니다..

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