11279번 - 최대 힙
아래 deletemax함수에 주석부분으로 표시해놨습니다.
일반적으로 힙의 구조를 유지하기 위해 생각해보면 당연히 있어야하는 코드지만,
적어도 해당 문제에서는 현재 노드가 자식노드 중 더 큰 노드보다 큰지 확인해야 할 필요가 있는지 모르겠습니다.
당연하게도 저 한줄 있고없고 정답이 갈렸구요.
저 코드가 없을 때, 힙 구조가 깨지는 케이스가 뭔지 알 수 있을까요 ?
조건문이 없으면 더 이상 교환할 필요가 없을 때도 교환하게 되어 결과가 바뀔 수 있습니다.
12 6 5 4 2 1 3 0 0 0 0 0 0
음 .. 그럴거라고 느낌은 오는데 구체적인 케이스가 떠오르진 않네요.
해당 케이스도 아래와 같이 출력이 잘 나옵니다.
주석처리하면 결과가 아래처럼 나오지 않나요?
제가 너무 덜렁댔네요 ..ㅋㅌㅋㅌ 주석처리하니 확실히 잘못된 값이 나옵니다.
반례 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
dlftmd03 10달 전
아래 deletemax함수에 주석부분으로 표시해놨습니다.
일반적으로 힙의 구조를 유지하기 위해 생각해보면 당연히 있어야하는 코드지만,
적어도 해당 문제에서는 현재 노드가 자식노드 중 더 큰 노드보다 큰지 확인해야 할 필요가 있는지 모르겠습니다.
당연하게도 저 한줄 있고없고 정답이 갈렸구요.
저 코드가 없을 때, 힙 구조가 깨지는 케이스가 뭔지 알 수 있을까요 ?