우선순위큐 썸네일형 리스트형 백준 1071번 소트 http://icpc.me/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 풀이 간단한 그리디 문제입니다. 사전순으로 앞선 배열을 만들어야 하기 때문에 앞에서 최대한 작은 수를 사용해야 합니다. 앞서 $i$개의 수를 최적으로 출력했다고 가정할 때 가능하다면 무조건 출력하지 않은 수 중 최솟값을 출력해야 하며, 최솟값을 출력할 수 없다면 두 번째로 작은 값을 출력해야 합니다. 최솟값을 출력할 수 없는 경우는 두 가지입니다. 1) $i$번째로 출력한 수 + 1 == 최솟값일 때 2) 출력하지 않은 수에서.. 더보기 백준 1655번 가운데를 말해요 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 N개의 정수를 입력받아 1번째, 2번째, ... N번째 정수까지만 보았을 때 각각의 중앙값들을 출력하는 문제입니다. 풀이 단순히 배열을 사용하여 입력받을 때마다 배열을 정렬한다면 O(N^2)이므로 시간초과일 것입니다. 힙을 이용하여 O(NlogN)으로 해결할 수 있습니다. 지금까지 입력받은 수 중 절반의 작은 수들은 최대 힙에, 나머지 절반의 큰 수들은 최소 힙에 저장합니다... 더보기 이전 1 다음
