replace 하는 방법이 시간초과가 나는 이유는
여러번의 문자열 이동으로 인한것이라고 생각됩니다.
aabcbc 에서 abc를 지우는 경우
a(abc)bc 의 괄호친 abc를 지울때 뒤에있는 bc를 앞으로 당겨오는 연산이 들어갈탠데, 이부분이 느릴 수 있습니다.
제가 푼 방법을 말씀드리자면
abc를 지울때 지운다음 합치지말고, 지웠다는 표시만 하는것입니다.
a___bc 같은 상태로 둔 다음 a 다음의 _를 만나면 실제 문자가 있는 b, c로 점프시키게 하는것으로 이동 시간을 줄였습니다.
dolpang2 7년 전
안녕하세요.
9935번 문제에서 질문 드립니다.
Naive 하게 생각했을 때 Python에서 제공하는 replace로 접근하면 될 것 같았는데
시간 초과가 나버리네요.
문제 분류를 보니 스택과 문자열 처리라고 하는데
알아야 하는 알고리즘이 따로 있나요?
그게 아니라면 어떤 식으로 접근하는지 힌트를 주시면 감사하겠습니다.