2075번 N번째 큰 수

코딩테스트 : 2075번 N번째 큰 수

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

12 MB (하단 참고)

43322

17558

12825

39.175%

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력

첫째 줄에 N번째 큰 수를 출력한다.

using System.Collections.Generic;
using System.Runtime.Intrinsics.X86;
using System.Text;

public class BackJoon
{
    static List<int> minHeap = new List<int>();

    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());

        int count = 0;

        for (int i = 0; i < n; i++)
        {
            int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
            for (int j = 0; j < n; j++)
            {
                int temp = arr[j];
                if (count < n)
                {
                    minHeap.Add(temp);
                    count++;
                }
                else if (count == n)
                {
                    minHeap.Sort();
                    count++;
                }
                else
                {
                    Compare(temp);
                }
            }
        }

        Console.WriteLine(minHeap[0]);


    }

    public static void Compare(int input)
    {
        int min = minHeap[0];

        if (input > min)
        {
            minHeap[0] = input;
            Heapify();
        }
        
    }

    public static void Heapify()
    {
        int currentIndex = 0;
        

        while (currentIndex < minHeap.Count)
        {
           int left = currentIndex * 2 + 1;
           int right = currentIndex * 2 + 2;
           
           int minIndex = currentIndex;

           if (left < minHeap.Count && minHeap[left] < minHeap[minIndex])
           {
               minIndex = left;
           }
           if (right < minHeap.Count && minHeap[right] < minHeap[minIndex])
           {
               minIndex = right;
           }

           if (minIndex != currentIndex)
           {
               Swap(minIndex, currentIndex);
               currentIndex = minIndex;
           }
           else break;
            
        }
    }
    
    
    
    public static void Swap(int a, int b)
    {
        (minHeap[a], minHeap[b]) = (minHeap[b], minHeap[a]);
    }
   
}

 

처음에 이 문제를 보고, 전혀 우선순위 큐를 떠올리지 못했다.

전부 다 넣으면서 비교해야하나... ? 생각했지만 , 결국 N개 이상의 수는 필요 없었다. 

 

 

다른 사람의 흥미로운 풀이

 

우선순위 큐를.. 사용하시는 분들, 이미 존재하는 라이브러리로 파신 분들이 계신다.