수학 + 큐 문제다 시물레이션으로 풀 수 있는데 숫자 범위가 int다 최악의 경우에 21억이 8개들어오면 대충 7억번? 돌아야한다고 생각하는데 그냥 풀어도 시간안에 들어오나보다 최악의 테케가 없는건지 아니면 내가 잘못생각한거지..! 어쨌든 문제는 5바퀴를돌면 총 15씩 전체적으로 감소시킬 수 있다 그럼 우리가 감소시킬 수 있는만큼 15*k만큼 감소시키자 그리고 시물을 돌리면 편하게 답이 나온다 직접 큐를 사용하지는 않는다 그냥 q의 top이 있다고 생각하고 top을 옮기는게 더 편하다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 import java.io.FileInputStream; imp..
총 N개의 입력이 들어오고 매번 입력마다 중간값을 출력하는 문제다 N이 최대 10만이기 때문에 N^2은 불가능하다! 자료구조 힙을 사용하면 된다 중간만 보기때문에 중간을 기준으로 양쪽을 힙으로 잘랐다고 생각하자 계속 첫번째 힙에 숫자를 넣어주고 만약 짝수번째 순서면 두번째 힙으로 넘겨주자 그리고 처리할게 하나 있는데 첫번째힙의 탑과 두번째 힙의 탑을 비교해서 첫번째 힙에 작은수가 들어갈 수 있게 해야한다 그럼 첫번째 힙의 top이 계속 답이된다! 참고로 첫번째는 max힙, 두번째는 min힙이다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace st..