at_dotist   4년 전

하루종일 만든 문자열을 큐에 넣고 최선의 문자열과 비교하는 방식으로 풀다보니 시간초과가 계속 나길래, 어느 순간 문자열을 비교하는 데 드는 비용을 알아봐야 겠다는 생각이 들더군요

문자열을 비교하는데 걸리는 시간이 문자열이 커지니 무시할 정도가 아니더라구요.

그래서 생각하다보니 어차피 정답이 될 문자열의 각 자리에는 올 수 있는 가장 큰 값이 들어있게 하면 되니 문자열 전체를 비교할 것이 아니라 그 위치에 있는 문자만 비교해서 이후에 올 수 있는 후보를 추리자라는 아이디어가 떠오르더군요.

문자열 채로 비교해서 시간초과가 난다면, 각 자리의 문자만 비교하는 방법을 생각해 보시면 문제를 푸시는데 도움이 될 듯 싶습니다.

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