백준 11286번 절대값 힙

문제 간단 설명

1. N개의 정수를 입력받는다.

2-1. 도중에 입력으로 0이 들어오면 저 지금까지 들어온 숫자 중에서 절대값이 가장 작은 수를 출력해준다.

2-2. 만약 절대값이 같은 수가 존재한다면(1과 -1과 같이), 실제 값이 더 작은 수를 출력해준다.(-1 출력)

시행착오 

arr[i][0]에는 절댓값 i의 음수 개수를, arr[i][1]에는 절댓값 i의 양수 개수를 저장해서 풀이를 하려고 했다. 하지만 입력값이 -2의 31승 ~ 2의 31승 인 점을 고려해서 arr의 1차원의 크기를 1<<31 - 1로 해줬더니 컴파일시에 너무 크다면서 오류가 발생했다. 

정답

priority_queue 는 비교하는 방식을 커스텀할 수 있다는 걸 알았다. 하지만 간단히 함수를 넣어서 비교할 수 있는게 아니라 cmp 클래스에서 operator를 오버라이팅한 후 cmp 클래스를 넘겨주는 방식이어서 복잡했다.

 

operator 에서 a, b가 인자로 들어온다. 만약 false를 리턴하면 순서가 a, b 그대로고, true를 리턴하면 b, a의 순서가 된다. -1, 4가 인자로 들어왔을 시 return abs(-1) > abs(4) == false 이므로 순서는 그대로이다.

2, -2가 인자로 들어왔을 시 return 2 > 0 && -2 < 0 == true 이므로 입력과 반대 순서로 swap된다.