알고리즘 코딩테스트 문제풀이 강의 - 14 절댓값 힙 구현하기 (백준 11286)

Question

C++ 책보고 풀어보고 있는데 이해가 안가는 부분이 있습니다. struct compare { bool operator()(int o1, int o2) { int first_abs = abs(o1); int second_abs = abs(o2); if (first_abs == second_abs) { return o1 > o2; } else { return first_abs > second_abs; } } }; return o1 > o2; 이 부분에서 현재 입력값이 1,-1,0 이렇게 들어오면 o1 = 1, o2 = -1이 들어와서 비교를 하여 1 > -1 되는거 아닌가요? 그럼 양수가 정렬이 되는데 어떻게 이해를 해야하는지 모르겠습니다. 우선순위 큐에 관해서 Compare에 찾아보니 작은 수를 반환한다고 하는데 왜 그런지 이해가 안가네요... 확인부탁드립니다. 마찬가지로 return first_abs > second_abs; 이 부분도 설명 부탁드립니다.

harucoding · Answer

안녕하세요. 먼저 해당 문제에 대한 풀이 강의 영상이 도움이 되실까 하여 공유드립니다. https://youtu.be/624DWEXSehw 재정의 방식은 각자 다르게 할 수 있기 때문에 항상 헷갈리긴합니다. 제가 쓰는 방법은 일단 고민하지말고 재정의 후 큐에 데이터를 출력하여 보았을때 오름차순인지 내림차순인지 보고, 내가 원하는 순서가 아니였다면 리턴값 부분만 반대로 주도록 설정하는 것입니다. (아마도 각자 자신의 취향대로 외우거나 저처럼 고민하지않고 구현 후 찍어보고 반대로 하거나 다 다를 것 같습니다. ^^) 비교 재정의 부분에 대해서 조금 더 자세히는 아래 영상에 정리하여 두었습니다. https://www.youtube.com/watch?v=zCpInXvVol0 먼저 우선순위 큐는 자바, 파이썬 오름차순 정렬이 기본으로 알고있고 C++의 경우는 내림차순으로 알고있습니다. 그리고 return 값이 참일 경우 두 데이터를 swap 해줍니다. 코드에 대해서 이해를 해보면 if (first_abs == second_abs) return o1 > o2 // 절댓값이 같으면 음수 우선 정렬한다. 현재 입력값이 1,-1 이렇게 되었을 때 return 1 > -1 이렇게 결국 값이 되고 해당 비교는 참입니다. 1이 -1보다 크기 때문에 return 값이 참 => swap을 해줍니다. 1 -1 => -1 1 로 정렬 return first_abs > second_abs; ; // 만약 앞의 if문 안을 수행 하지 않았다면 ( 즉 절댓값이 다른 경우, 절댓 값이 작은 수 기준으로 정렬한다.) 이 구문을 보면 예를들어 -3 5가 들어왔다고 가정하면 절대값으로 치환한 후 3 > 5 가 되고 이러면 비교 결과가 거짓이기 때문에 그대로 둡니다. -3 ,5 => 그래도 -3, 5 https://travelbeeee.tistory.com/126 여기에도 비슷하게 설명해주신 분이 있네여.