최소힙

오늘 살펴볼 문제는 백준 1655번 문제이다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다. N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나? 라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)..
DevOwen
'최소힙' 태그의 글 목록