-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
알고리즘 코딩테스트 문제풀이 강의 - 14 절댓값 힙 구현하기 (백준 11286)
23.04.26 15:39 작성 조회수 356
0
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; 이 부분도 설명 부탁드립니다.
답변을 작성해보세요.
0
하루코딩
지식공유자2023.04.26
안녕하세요. 먼저 해당 문제에 대한 풀이 강의 영상이 도움이 되실까 하여 공유드립니다.
재정의 방식은 각자 다르게 할 수 있기 때문에 항상 헷갈리긴합니다. 제가 쓰는 방법은 일단 고민하지말고 재정의 후 큐에 데이터를 출력하여 보았을때 오름차순인지 내림차순인지 보고, 내가 원하는 순서가 아니였다면 리턴값 부분만 반대로 주도록 설정하는 것입니다. (아마도 각자 자신의 취향대로 외우거나 저처럼 고민하지않고 구현 후 찍어보고 반대로 하거나 다 다를 것 같습니다. ^^) 비교 재정의 부분에 대해서 조금 더 자세히는 아래 영상에 정리하여 두었습니다. 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 여기에도 비슷하게 설명해주신 분이 있네여.
답변 1