2696번 중앙값 구하기
코딩테스트 : 2696번 중앙값 구하기
| 1 초 | 128 MB | 10306 | 5007 | 3922 | 50.334% |
문제
어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오.
예를 들어, 수열이 1, 5, 4, 3, 2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다.
입력
첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주어진다. 원소는 한 줄에 10개씩 나누어져있고, 32비트 부호있는 정수이다.
출력
각 테스트 케이스에 대해 첫째 줄에 출력하는 중앙값의 개수를 출력하고, 둘째 줄에는 홀수 번째 수를 읽을 때 마다 구한 중앙값을 차례대로 공백으로 구분하여 출력한다. 이때, 한 줄에 10개씩 출력해야 한다.
using System.Collections.Generic;
using System.Runtime.Intrinsics.X86;
using System.Text;
public class BackJoon
{
// 2696번 중앙값 구하기
static List<int> maxHeap= new List<int>();
static List<int> minHeap= new List<int>();
private static int middle = 0;
public static void Main()
{
// 아이디어 : 중앙값을 Pop해야 한다, 그러므로 왼쪽 오른쪽을 따로 유지하여 왼쪽에서는 최댓값 힙,
// 오른쪽에서는 최솟값 힙을 구현하여 Pop 되는 수가 중앙값임을 보장한다.
// 왼쪽과 오른쪽의 수가 같게 만들어야 한다, 어느 한쪽에 들어갔으면 다음번 수는 반대쪽에 넣어야 한다. ( 홀수 )
// 혹은 어느 한 쪾에 두 번 들어간다면, 맨 위에 있는 것을 빼서 반대쪽에 추가해 주어야 한다.
// 테스트 케이스 개수
int n = int.Parse(Console.ReadLine());
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
{
int tempCase = int.Parse(Console.ReadLine());
List<int> tempArr = new List<int>();
while (tempArr.Count < tempCase)
{
tempArr.AddRange(Console.ReadLine().Split(' ').Select(int.Parse));
}
minHeap.Clear();
maxHeap.Clear();
middle = tempArr[0];
sb.AppendLine((tempCase / 2 + 1).ToString());
int outputCount = 0;
sb.Append(middle + " ");
outputCount++;
for (int j = 1; j < tempCase; j++)
{
int temp = tempArr[j];
// 왼쪽 오른쪽에 넣기
if (temp < middle)
{
maxHeap.Add(temp);
HeapifyUpLeft();
}
else
{
minHeap.Add(temp);
HeapifyUpRight();
}
//균형 맞추기
if (maxHeap.Count > minHeap.Count)
{
minHeap.Add(middle);
HeapifyUpRight();
middle = maxHeap[0];
maxHeap[0] = maxHeap[maxHeap.Count - 1];
maxHeap.RemoveAt(maxHeap.Count - 1);
if (maxHeap.Count > 0) HeapifyDownLeft();
}
else if ( maxHeap.Count < minHeap.Count)
{
maxHeap.Add(middle);
HeapifyUpLeft();
middle = minHeap[0];
minHeap[0] = minHeap[minHeap.Count - 1];
minHeap.RemoveAt(minHeap.Count - 1);
if ( minHeap.Count > 0) HeapifyDownRight();
}
if ((j + 1) % 2 == 1)
{
sb.Append(middle + " ");
outputCount++;
if ( outputCount % 10 == 0) sb.AppendLine();
}
}
if (outputCount % 10 != 0) sb.AppendLine();
}
Console.WriteLine(sb.ToString());
}
public static void HeapifyUpRight()
{
int tempIndex = minHeap.Count - 1;
while (tempIndex > 0)
{
int parent = (tempIndex - 1) / 2;
if (minHeap[tempIndex] < minHeap[parent])
{
Swap(minHeap, tempIndex, parent);
tempIndex = parent;
}
else break;
}
}
public static void HeapifyUpLeft()
{
int tempIndex = maxHeap.Count - 1;
while (tempIndex > 0)
{
int parent = (tempIndex - 1) / 2;
if (maxHeap[tempIndex] > maxHeap[parent])
{
Swap(maxHeap, tempIndex, parent);
tempIndex = parent;
}
else break;
}
}
public static void HeapifyDownLeft()
{
int tempIndex = 0;
int maxIndex = tempIndex;
while (tempIndex < maxHeap.Count)
{
int left = tempIndex * 2 + 1;
int right = tempIndex * 2 + 2;
if ( left < maxHeap.Count && maxHeap[left] > maxHeap[maxIndex]) maxIndex = left;
if (right < maxHeap.Count && maxHeap[right] > maxHeap[maxIndex]) maxIndex = right;
if (tempIndex != maxIndex)
{
Swap(maxHeap, tempIndex, maxIndex);
tempIndex = maxIndex;
}
else break;
}
}
public static void HeapifyDownRight()
{
int tempIndex = 0;
int minIndex = tempIndex;
while (tempIndex < minHeap.Count)
{
int left = tempIndex * 2 + 1;
int right = tempIndex * 2 + 2;
if ( left < minHeap.Count && minHeap[left] < minHeap[minIndex]) minIndex = left;
if ( right < minHeap.Count && minHeap[right] < minHeap[minIndex]) minIndex = right;
if (tempIndex != minIndex)
{
Swap(minHeap, tempIndex, minIndex);
tempIndex = minIndex;
}
else break;
}
}
public static void Swap(List<int> list, int a, int b)
{
(list[a], list[b]) = (list[b], list[a]);
}
}
지금까지 풀었던 문제 중 가장 길게... 써서 풀었던 문제다.
우선순위 큐를 쓴다면 훨씬 편하게 풀었겠지만, 일단 내 손으로 해 보고 싶었다.
그래서 풀고 나서 다시 풀 문제에 적어두고, 그때는 우선순위 큐로 풀 예정이다.
아이디어는 다음과 같다.
1. 수열의 안에 들어 있는 수가 홀수일 때, '중앙값'을 기준으로 좌우의 원소의 개수는 항상 같아야 한다.
2. 전체를 우선순위 큐로 만들 수 없으니, 왼쪽은 최대값 큐, 오른쪽은 최소값 큐로 만들고, 중앙값은 따로 설정해둔다.
3. 수가 들어오면, 중앙값과 비교한 후 , 작으면 왼쪽에, 크면 오른쪽에 넣고 정렬한다. ( 매 번 정렬이 필요하다 )
4. 정렬하고, 두 우선순위 큐의 차이가 1 이상이면 ( 한 쪽으로 두 번 들어갔으면 ) 큰 쪽에서 하나를 빼서 미들에 놓고, 미들을 반대쪽에 넣고 정렬한다.
처음부터 아이디어 자체는 거의 맞았는데 , 계속해서 오류가 나서 , 예외처리를 하는데 시간이 오래걸렸다.
개선점
위의 코드는 매 번 왼쪽과 오른쪽을 비교하지만 다음과 같이 한 쪽으로 두 번 이상 몰렸을 때 정렬하는 것이 효율적이다.
//균형 맞추기
if (maxHeap.Count > minHeap.Count + 1)
{
minHeap.Add(middle);
HeapifyUpRight();
middle = maxHeap[0];
maxHeap[0] = maxHeap[maxHeap.Count - 1];
maxHeap.RemoveAt(maxHeap.Count - 1);
if (maxHeap.Count > 0) HeapifyDownLeft();
}
else if ( maxHeap.Count + 1 < minHeap.Count)
{
maxHeap.Add(middle);
HeapifyUpLeft();
middle = minHeap[0];
minHeap[0] = minHeap[minHeap.Count - 1];
minHeap.RemoveAt(minHeap.Count - 1);
if ( minHeap.Count > 0) HeapifyDownRight();
}
처음에 이게 오류뜨는줄 알고 고쳤다가 ,다시 고치는걸 깜빡했다 ㅎ, 테스트 해 보니 정상 동작한다.
두 번째로 여기서 더 개선할 수 있는 점은 공통 부분을 묶어서 새로운 함수로 만들면 편하다는 것이다.
public static void ReplaceRoot(List<int> heap, Action heapifyDown)
{
if (heap.Count == 0) return;
heap[0] = heap[heap.Count - 1];
heap.RemoveAt(heap.Count - 1);
heapifyDown();
}다음 함수처럼 , 루트로 새로운 수를 넣었을 때의 함수를 정의한다면, 조금 더 간결하게 코드를 작성할 수 있다 .
Action을 넣는 것은 생각하지 못해서 이걸 생각하지 못했었는데, 다음부터는 조금 더 고려해봐야겠다.
다른 사람의 흥미로운 풀이
우선순위 큐를 하나만 사용해서 푸신 분이 계신다.
어떻게.. ? 우선순위 큐가 정확하게 어떻게 동작하는지 모르기 때문에 일단 저장해두었다. 나중에 다시 풀 때 더 자세하게 봐야겠다.
대부분의 분들이 우선순위 큐를 사용하셔서 푸셨기에 , 다음에 풀 때는 우선순위 큐를 사용할 예정이다.