본문 바로가기

TIL/코테 스터디

99클럽 코테 스터디 20일차 TIL: 빠른입출력

반응형

문제

https://www.acmicpc.net/problem/2075

풀이

Swift는 입출력이 느려 Fread 방식으로 구현된 빠른 입력을 사용해야 한다.
빠른 입력만 사용해서 정렬해서 N번째 큰수를 구하는 방법도 있겠지만, Heap을 사용해서 풀이하는 방법이 있다.

일반적으로 정렬은 $NlogN$의 시간복잡도를 띄는데, 힙의 pop연산은 $logN$이므로 우선순위 큐를 사용하는 편이 일반적으로 더 빠를 것이라고 생각했다.

힙은 전날 풀이한 코드에 올려두어서 생략하고 동일한 코드를 사용하여 풀었다.

소스코드

후기

빠른입력을 사용하면 쉽게 풀 수 있는 문제.
백준에서 입력값이 크면 Swift 시간을 좀 늘려주면 좋겠다..

반응형