최대 20 만개 숫자중에 젤큰거 3개 가 필요해
1번 리스트에 다 때려박고 내림차 정렬
삽입 O(n) 정렬 O(nlogn)
2번 우선순위큐 오름차정렬 로 만들어놓고
넣으면서 사이즈 4 이상 일때 하나씩 버리기
삽입 O(nlog4) 추출 O(nlog4)
2번으로했는데 속도차 있을까?
최대 20 만개 숫자중에 젤큰거 3개 가 필요해
1번 리스트에 다 때려박고 내림차 정렬
삽입 O(n) 정렬 O(nlogn)
2번 우선순위큐 오름차정렬 로 만들어놓고
넣으면서 사이즈 4 이상 일때 하나씩 버리기
삽입 O(nlog4) 추출 O(nlog4)
2번으로했는데 속도차 있을까?
2번이 더 빠를거 같은데
나두 느낌은 2번인데 확신이 읎어서
한 번 하고 말 작업이면 애초에 왜 자료구조에 담음?
2번에서 4개까지만 들고 있겠다고 하는 거 보니까 top3 말고는 필요 없나본데 그럼 O(n) 아님 걍?
숫자가 하나씩 오는데 글면 젤큰거 3개 어케 골라냄
힙모름?
힙에 넣을 필요도 없고 걍 젤 큰 거 3개를 배열에만 저장해둬도 되잖아?
그니까 젤큰지 아닌지 어케 판별할껀데
새로운 숫자 들어올 때마다 대소비교 최대 3번만 하면 되는구만
어 글면 3n 이니까 상수버리고 O(n) 되는건가?
네
ㄱㅅㄱㅅ