명예의 전당 (1) (c++)

sol

1. k번까지는 비교 없이 전부 넣고 sort

2. k번 이후부터는 최소값이랑 비교해서 크면 sort, 아니면 continue

고민

• 우선순위 큐를 사용하는 방법도 가능하다고 한다. 
• 벡터를 정렬하나 우선순위 큐를 사용하나 시간복잡도는 동일한데, 벡터를 사용할 경우에 조금 더 느리다.

vector sort	priority_queue
vector sort : O(nlogn) push_back() : O(1)	push : O(nlogn) pop : O(nlogn) 최상위 요소 접근 : O(1)
score size() 만큼 for문 반복 : O(n) 명예의 전당에 올라가는 값 push : O(nlogn) sort() : O(nlogn) v[0]에 접근 : O(1) => O(n * nlogn)	score.size() 만큼 for문 반복 : O(n) 명예의 전당에 올라가는 값 push : O(nlogn) 명예의 전당 최상위 값 접근 : O(1) answer에 push_back : O(1) 최상위 값보다 클 경우, pop : O(nlogn) => O(n * nlogn)

• push_back을 사용할 때, vector의 크기를 넘어서면, 2배 정도 더 큰 용량의 메모리를 할당한 후, 기존 원소를 모두 복사하고, 기존의 메모리는 해제하는 작업을 거쳐서 최악의 경우 O(n)까지 시간복잡도가 늘어난다고 한다.
  [C++] vector의 reserve()로 push_back() 시간을 줄이자! (tistory.com)
• push_back()으로 answer에 값을 넣었던 걸 크기를 할당해서 random access해보니 대부분 줄어들었다. (늘어난 것도 있기는 하다.. 왤까..?)
• 우선순위 큐를 쓸 때는 answer에서 push_back을 random access로 변경할 수는 있지만, 벡터를 정렬하는 방식으로 하면, k일까지의 vector를 만들 때, push_back을 사용해야해서 더 느린 걸로 보인다.
• vector를 처음 만들 때 크기를 지정해줄 수 있기는 한데, 오히려 시간이 느리다. 벡터의 길이를 n이라 두고 정렬할 때, O(nlogn)이니까 짧은 길이를 정렬할 때는 오히려 벡터의 길이를 길게 두는 게 길게 걸리는 것 같다.
• 들어오는 값이 100개면? push_back()하면 초반에는 작은 길이의 벡터를 정렬할 수 있는데, 길이를 할당해버리면 100의 길이의 벡터를 정렬해야하니까

결론
상황에 따라서는 push_back() 대신에 고정 길이로 초기화하자.
계속 값을 넣었다 뺐다하는 경우 vector보다는 priority_queue가 나을 수 있다.

	push_back	random access
vector
priority_queue

 

우선순위 큐와 벡터 정렬 시간복잡도 차이 - Priority queue vs Vector sort :: 딩코딩 : Computer Science 블로그 (tistory.com)

[C++][자료구조] 우선순위 큐(Priority Queue) (velog.io)

shin0112/programmers_cpp: programmers' coding test solutions (github.com)

출처 : 프로그래머스 코딩 테스트 연습 - 명예의 전당 (1)
https://school.programmers.co.kr/learn/courses/30/lessons/138477