17299번 - 오등큰수
우선순위 큐를 사용하면 해결할 수 있습니다.
현재 수의 오른쪽 만 살펴보면 되니, 배열을 뒤에서 부터 순회해 줍니다.
이 때 현재 수 의 오른쪽 수 들 중 현재 수의 등장 횟수 보다 적게 등장한 수는 필요 없습니다.
그 이유는, 현재 수의 왼쪽 수 에서 바라볼 때 현재 수 보다 적게 등장한 횟수의 수 들은 선택될 수 없기 때문입니다.
예를들어, 현재 수가 5번 등장했고 현재 수 의 오른쪽에 3번 등장한 수가 있다면, 앞으로 3번 등장한 수는 선택될 수 없습니다.
왜냐하면 현재 수가 3번 보다 더 큰 5번 등장했고 더 오른쪽에 가까이 있기 떄문입니다.
이 특징을 이용하여 최소 힙 을 갱신해가면 됩니다.
댓글을 작성하려면 로그인해야 합니다.
helios789789 3년 전 1
우선순위 큐를 사용하면 해결할 수 있습니다.
현재 수의 오른쪽 만 살펴보면 되니, 배열을 뒤에서 부터 순회해 줍니다.
이 때 현재 수 의 오른쪽 수 들 중 현재 수의 등장 횟수 보다 적게 등장한 수는 필요 없습니다.
그 이유는, 현재 수의 왼쪽 수 에서 바라볼 때 현재 수 보다 적게 등장한 횟수의 수 들은 선택될 수 없기 때문입니다.
예를들어, 현재 수가 5번 등장했고 현재 수 의 오른쪽에 3번 등장한 수가 있다면, 앞으로 3번 등장한 수는 선택될 수 없습니다.
왜냐하면 현재 수가 3번 보다 더 큰 5번 등장했고 더 오른쪽에 가까이 있기 떄문입니다.
이 특징을 이용하여 최소 힙 을 갱신해가면 됩니다.