hoonzi   3년 전

문제의 의도는 heap을 사용해라 인듯 한걸 알지만 잘 모르겠어서

dictionary로 풀었습니다.

{

"1" : 1의 count,

"2" : 2의 count, 

...

} 

인데 통과했네요 참고하세용

bupjae   3년 전

이론적으로 "최적"해는 min-max heap 이며

sorted multiset 을 사용해도 비슷한 시간복잡도로 해결할 수 있습니다.

이러한 자료 구조들은 삽입, 최대값 삭제, 최소값 삭제를 모두 O(log n) 시간복잡도로 수행할 수 있습니다. 

   

작성하신 프로그램은 (스스로 정렬하는 기능이 없는) dict 를 사용하고 있는데,

이 경우 삽입은 O(1) 이지만 최대값/최소값 삭제는 O(n) 입니다.

    

이 문제는 다른 문제에 비해 제한시간이 넉넉하게 설정되어 있는데, 삭제 연산의 시간복잡도가 O(n)인 구현도 충분히 통과할 수 있는 수준으로 보입니다.

글 읽기 - 시간을 줄여 주세요. (acmicpc.net) 글에서 제한시간을 줄여야 한다는 요청이 있는데, 이 요청이 받아들여진다면 이 프로그램은 높은 확률로 "시간 초과"를 받게 될 것입니다.

hoonzi   3년 전

친절하고 자세한 답변 감사드립니다.

알려주신 알고리즘을 공부해보겠습니다!


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