lesk012   1년 전

4%에서 시간초과가 납니다

while안에서 for문으로 완전탐색을 하기 때문인 것 같습니다. 어떻게 개선하면 좋을까요?

또한 알고리즘이 정확한지 궁금합니다. 찾아본 반례들은 통과하는데, 제출하면 4%에서 걸리니 더 알 수가 없네요 ㅠㅠ

bug_hunter   1년 전

제가 랜덤으로 인풋 생성하면서 정답 코드랑 아웃풋 비교 해봤는데

큰 인풋에 대해서도 다르지 않은 걸 보니 알고리즘이 틀린 것 같진 않고요.

시간 복잡도가 좀 큰 것 같네요.

참고로 백준저지는 시간 초과를 먼저 유도하기 위해

채점 데이터의 크기가 큰 것부터 채점을 진행합니다.

4%면 아마 대략 25개의 인풋 파일들이 있는데

그 중 첫 번째로 시도한 파일에서 시간 초과가 난 걸 거예요.

-

저는 라인 스위핑 기법으로 이 문제를 풀었고요.

우선순위 큐를 안쓰고 풀어서 그런지,

작성하신 코드가 어떤 의도인지는 대강 감은 잡히는데..

어떻게 개선할지는.. 잘 모르겠네요ㅠㅠㅠㅠ

혹시 어떤 의도로 우선순위 큐를 쓰려고 하신 건지

알 수 있을까요..?

-

다른 질문 있으시면 편하게 주셔도 됩니다. :)

dlgusrb3456   1년 전

혹시 제 질문도 한번 봐주실수 있을까요 ㅠ

lesk012   1년 전

@bug_hunter 님 확인 감사합니다

우선순위 큐를 사용한 이유는 그저 문제의 알고리즘 분류에 있었기 때문입니다.

라인 스위핑 기법은 처음 들어보는데, 공부해보고 다시 풀어봐야겠네요 :)

이번에도 감사합니다 !

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