helios789789   1년 전

우선순위 큐를 사용하면 해결할 수 있습니다.

현재 수의 오른쪽 만 살펴보면 되니, 배열을 뒤에서 부터 순회해 줍니다.

이 때 현재 수 의 오른쪽 수 들 중 현재 수의 등장 횟수 보다 적게 등장한 수는 필요 없습니다.

그 이유는, 현재 수의 왼쪽 수 에서 바라볼 때 현재 수 보다 적게 등장한 횟수의 수 들은 선택될 수 없기 때문입니다.

예를들어, 현재 수가 5번 등장했고 현재 수 의 오른쪽에 3번 등장한 수가 있다면, 앞으로 3번 등장한 수는 선택될 수 없습니다.

왜냐하면 현재 수가 3번 보다 더 큰 5번 등장했고 더 오른쪽에 가까이 있기 떄문입니다.

이 특징을 이용하여 최소 힙 을 갱신해가면 됩니다.

댓글을 작성하려면 로그인해야 합니다.