NAMING 어떻게 접근하나요?

  • Andromeda
    Andromeda

    http://www.algospot.com/problems/read/NAMING

    시간 제한이 500 ms인 것을 보면 아무래도 O(N)에 해당하는 방법이 있을 것 같기도 한데요.
    제 머리로는 O(N^2)이 한계네요.

    Naive하게 풀면 당연히(?) 시간 초과되고요.
    LCS도 생각은 해봤는데, 뭔가 많이 뜯어 고치지 않는한, O(N^2)인 것 같고요.
    (일단 N^2만 떠올라서 굳이 짜보지는 않았네요.)
    substring에서 strstr로 기존까지 찾은 가장 큰 prefix를 찾은 다음,
    그것이 조건을 만족하는지 확인하는 식으로 하는 방법도 생각했지만,
    발로 짜서 그런지 역시 안 되네요.

    제가 초보 중의 초보, 잉여 중의 잉여라 잘 생각이 안 떠오르네요.
    어떻게 풀면 O(N)이나 O(N log N)에 될까요?


    13년 전
4개의 댓글이 있습니다.
  • okioki007
    okioki007

    KMP 알고리즘에서 failure function 참고하세요!


    13년 전 link
  • Andromeda
    Andromeda

    답변 감사합니다.
    그런데 "작명하기"로 검색하면 같은 글이 있었네요. ㅠㅠ
    "작명"으로 검색하면 안 나와서 없는 줄 알았어요. ㅠㅠ


    13년 전 link
  • Chulman
    Chulman

    이 문제 자바로 푼 사람 한명도 없나요?
    시간 초과되는데; 제출한 사람중에서도 자바가 없네요.


    12년 전 link
  • Being
    Being

    http://algospot.com/forum/read/1384/ 이 논의를 참조하세요.


    12년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.