이 문제는 덱을 사용하여 O(N)에 푸는 방법이 존재하고, 사실 우선순위 큐를 통과시키고 싶어하지 않았습니다. 2.4초라는 애매한 제한은 본래 우선순위 큐 풀이를 어느 정도 막기 위해 설정된 제한입니다.
하지만 우선순위 큐에 의한 log(N)에 비해 입출력의 오버헤드가 너무 커서, 입출력을 충분히 빠르게 한다면 우선순위 큐를 사용해도 충분히 통과가 가능합니다. scanf, printf는 충분히 빠르지 않습니다.
11003번 - 최솟값 찾기
이 문제는 덱을 사용하여 O(N)에 푸는 방법이 존재하고, 사실 우선순위 큐를 통과시키고 싶어하지 않았습니다. 2.4초라는 애매한 제한은 본래 우선순위 큐 풀이를 어느 정도 막기 위해 설정된 제한입니다.
하지만 우선순위 큐에 의한 log(N)에 비해 입출력의 오버헤드가 너무 커서, 입출력을 충분히 빠르게 한다면 우선순위 큐를 사용해도 충분히 통과가 가능합니다. scanf, printf는 충분히 빠르지 않습니다.
댓글을 작성하려면 로그인해야 합니다.
ksjb2897 1년 전
우선순위큐로 짜봤습니다.
numb라는 자료형은, 수의 값 value와 이 수가 힙에서 존재하는지 나타내는 exist로 구성했습니다.
나중에 힙에서 뺄 때 힙 중간에 있는 원소를 빼기가 어려워서 exist를 넣었어요!
그리고 heap을 numb를 가리키는 포인터로 구성했습니다.
그렇게 해서 처음에 배열에 수들을 받으면서, heap에 넣고,
길이가 L이 될 때, 하나씩 넣고 하나씩 빼는 식으로 진행했습니다.
이 때, 넣을 때는 그냥 뒤에 원소를 넣고, 뺄 때는 앞의 원소의 주소로 찾아가 exist를 0으로 만들었습니다. 그러고 나서 heap[1]의 exist가 1이될때까지 (즉, heap에 존재하는 최솟값보다 작은, 이미 없어진 원소들을 다 heap에서 뺄 때까지) heap[1]을 pop했습니다. 이렇게 되면 heap[1]은 heap안에 존재하는 원소이면서 젤 작은 수가 되기 때문에 출력합니다!
testcase.ac에서 테스트해봐도 반례가 없는데,
3퍼센트에서 시간초과가 나네요..
제가 생각하기엔 이 방법의 시간복잡도가 NlogN인거 같은데... 왜 틀렸을까요..? ㅠㅠ
다른분들도 NlogN 으로 구현하고 시간초과가 난다는 분도 있는데 또 댓글에는 잘 구현하면 된다고 하더라구요..
아니면 혹시 제 코드가 while문에 갇혀서 시간초과가 날 가능성이 있을까요?
push(numb* nod)는 말 그대로 수를 heap에 넣는 함수이고,
pop(int k)는 k번째 인덱스에 있는 수의 exist를 0으로 만들고 heap[1]의 exist가 1이 될때까지 원소들을 다 빼내는 함수입니다.\
고수님들 도와주세요 ㅠㅠ