wodus0129   3년 전

다음과 같이 작성했는데 시간초과가 발생합니다.....

무엇이 문제인가요?

dps2   3년 전

코드를 보면 문자열의 임의의 문자에 대하여 해당 문자가 등장한 횟수를 count 메서드를 이용하여 여태까지 가장 많이 등장한 문자의 등장 횟수와 비교하고 있습니다.

그런데 count가 어떻게 작동되는지 살펴보자면 문자열의 문자들을 하나하나 다 보면서 등장 횟수를 셉니다.


시간복잡도를 아신다면 count 자체에 O(n)이 들어가니까 이 코드의 시간 복잡도는 O(n^2)입니다.

문자열의 최대 길이가 백만이니까 O(n^2)은 시간초과가 뜰 수 밖에 없습니다.

문자열의 각 문자에 대해서 또 다시 문자열의 각 문자를 보는 방식 외에 다른 효율적인 방법을 생각하시면 좋을 것 같습니다.

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