jh05013   5년 전

스택 입문용으로 쓰기엔 너무 어려운 문제라고 생각하는데 왜 이렇게 인기가 많은지...

내장함수의 시간복잡도를 숙지합시다. 여기 올라오는 대부분의 시간 초과 질문은 내장함수를 잘못 사용하여 O(N^2)의 시간복잡도를 가지는 질문입니다. 예를 들면 (이외에도 수많은 경우가 있습니다)

  1. C의 strlen
  2. C++의 string.erase
  3. Java의 String.replaceAll
  4. Python의 str.replace, str.find, list.pop(i), list.index, ''.join, [:i], [i:]
  5. 굳이 내장함수가 아니더라도 단순히 문자열의 중간을 한 번 지울 때마다 거의 무조건 O(N)이 걸립니다. 직접 구현한 코드의 시간복잡도를 계산해 보세요.

런타임 에러의 경우 인덱스 참조에 유의합시다.

그리고 FLURA가 아니라 FRULA입니다.

jh05013   3년 전

그리고 자주 틀리는 요인과는 관계 없지만, 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않습니다. 지나치기 쉬운 조건이라서 강조해 둡니다.

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