attack1021   1년 전

priority queue 같은 자료형 사용하지 않고 배열로 힙을 구현했습니다.

testcase.ac 에서 채점해봤을때는 테스트케이스 1개 빼고 다 통과해서 로직자체는 맞는거 같은데, 시간초과가 떠서 질문드립니다...!

ps. priority queue 를 사용했더니 성공을 받았습니다. 배열로 직접 만든 힙과 priority queue 와의 시간차이가 왜 발생하는지가 궁금합니다...ㅠㅠ

azruine   1년 전

1개를 빼고 통과했다는게, 한 개의 케이스에서 틀렸다는 뜻인가요? 하나라도 틀렸다면 로직이 틀린 것입니다.

heap의 pop 과정에서, 맨 마지막 if 문의 else break가 없어서 무한 루프를 도는 것 같네요.

attack1021   1년 전

한 개의 케이스에서만 시간초과가 납니다 ㅠㅠ

break 는 루프가 진행될수록 index가 반드시 커지는 구조이기 때문에 break가 날수밖에 없을거같긴해요...

azruine   1년 전

http://boj.kr/101508399a6b4a6c...
위 코드에서 else break; 만 추가한 코드입니다. 428ms로 AC를 받습니다.

배열이 이미 정렬되어 있는 상황에서 탈출할 수 있는 경로가 없습니다.

[_, 9, 8, 7, 6], idx = 1

idx * 2 , idx * 2 + 1 < 4 이므로 첫 두 if 문 실행 안됨

next 는 8의 인덱스인 2 선정

compare(9, 8) 실행 시 true 반환, if 문 실행 안됨

다시 while(true)로 돌아가는데, idx 변경이 없으므로 무한 루프

한 개의 케이스가 틀렸다는 것은 결국 이 코드가 어떤 상황에서는 오답을 낸다는 뜻입니다. 주어진 상황에서 어딘가 논리적으로 틀렸다는 것이고, 그래서 로직이 틀렸다는 것입니다.

attack1021   1년 전

아하 정말 감사합니다!

azruine 님이 추가하신 코드를 보고나서 제 코드가 뭐가 문제인지를 깨달았습니다...

다음부터는 더 꼼꼼히 살펴보겠습니다 ㅠㅠ 정말 감사해요!

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