11279번 최대 힙, 1927번 최소 힙 , 11286번 절댓값 힙

코딩테스트/백준

11279번 최대 힙, 1927번 최소 힙 , 11286번 절댓값 힙

Cadi 2025. 4. 21. 14:44

코딩테스트 : 11279번 최대 힙

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

1 초 (추가 시간 없음) (하단 참고)

256 MB

93374

45684

36296

50.413%

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

using System.Runtime.Intrinsics.X86;

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

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

        // 안의 순서가 전부 다 정렬되어 있을 필요는 없다, 맨 위에 있는 것만 가장 큰 숫자면 된다.
        for (int i = 0; i < n; i++)
        {
            int temp = int.Parse(Console.ReadLine());

            if (temp != 0)
            {
                maxHeap.Add(temp);
                int index = maxHeap.Count - 1;
                while (index > 0)
                {
                    int parentIndex = (index - 1) / 2;
                    if (maxHeap[index] > maxHeap[parentIndex])
                    {
                        Swap(index, parentIndex);
                        index = parentIndex;
                    }
                    else break;
                }
            }
            else
            {
                if (maxHeap.Count > 0) Console.WriteLine(Pop());
                else Console.WriteLine(0);
            }
        }
    }


    static public int Pop()
    {
        int largest = maxHeap[0];
        int lastIndex = maxHeap.Count - 1;

        if (lastIndex == 0)
        {
            maxHeap.RemoveAt(0);
            return largest;
        }

        maxHeap[0] = maxHeap[lastIndex];
        maxHeap.RemoveAt(lastIndex);
        HeapDown(0);

        return largest;
    }

    public static void HeapDown(int index)
    {
        while (index < maxHeap.Count)
        {
            int left = 2 * index + 1;
            int right = 2 * index + 2;

            if (left < maxHeap.Count && maxHeap[left] > maxHeap[index])
            {
                Swap(index, left);
                index = left;
                continue;
            }

            if (right < maxHeap.Count && maxHeap[right] > maxHeap[index])
            {
                Swap(index, right);
                index = right;
                continue;
            }

            break;
        }
    }

    public static void Swap(int a, int b)
    {
        (maxHeap[a], maxHeap[b]) = (maxHeap[b], maxHeap[a]);
    }
}

세 가지 때문에 한참 걸렸다.

1. 조건 비교에서 먼저 인덱스가 범위를 벗어나는지

if (maxHeap[left] > maxHeap[index] && left < maxHeap.Count)

처음에는 이런 방식으로 비교를 했다. 그런데 이런 방식으로 비교를 하다 보면

maxHeap[left]를 먼저 접근하기 때문에 left가 maxHeap.Count 보다 크다면 오류가 발생하게 된다.

&& 연산자에서 왼쪽이 먼저 접근되기 때문에, 선행되어야 하는 조건이 있다면 먼저 써 주어야 한다.

2. HeapDown에서 가장 큰 숫자가 위로 가지 않는 문제

현재 코드에선 왼쪽이 부모보다 크다면 바로 바꿔버리고 다음 과정을 수행한다.

이렇게 된다면 예를 들어 부모 , 왼쪽, 오른쪽 순서대로 10 , 20, 30이 있다면 20이 부모가 되는 문제가 발생한다.( 30이 되어야 함)

그래서 왼쪽 오른쪽을 다 비교하고, 가장 큰 숫자를 위로 올려야 한다.

3. 위 두 가지 사항을 고치고 나서 아무리 생각해도 정답인데 안되길래 한참을 고민했다.

보니까.... 반복하는 동시에 출력을 하고 있어 순서가 얽혀서 출력되는 것이 문제였다.

StringBuilder로 고쳐 주었다.

using System.Collections.Generic;
using System.Text;

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

    public static void Main()
    {
        StringBuilder sb = new StringBuilder();
        maxHeap.Clear();
        int n = int.Parse(Console.ReadLine());

        // 안의 순서가 전부 다 정렬되어 있을 필요는 없다, 맨 위에 있는 것만 가장 큰 숫자면 된다.
        for (int i = 0; i < n; i++)
        {
            int temp = int.Parse(Console.ReadLine());

            if (temp != 0)
            {
                maxHeap.Add(temp);
                int index = maxHeap.Count - 1;
                while (index > 0)
                {
                    int parentIndex = (index - 1) / 2;
                    if (maxHeap[index] > maxHeap[parentIndex])
                    {
                        Swap(index, parentIndex);
                        index = parentIndex;
                    }
                    else break;
                }
            }
            else
            {
                if (maxHeap.Count > 0) sb.AppendLine(Pop().ToString());
                else sb.AppendLine( 0.ToString());
            }
        }
        Console.WriteLine(sb.ToString());
    }


    static public int Pop()
    {
        int largest = maxHeap[0];
        int lastIndex = maxHeap.Count - 1;

        if (lastIndex == 0)
        {
            maxHeap.RemoveAt(0);
            return largest;
        }

        maxHeap[0] = maxHeap[lastIndex];
        maxHeap.RemoveAt(lastIndex);
        
        HeapDown(0);

        return largest;
    }

    public static void HeapDown(int index)
    {

        while (index < maxHeap.Count)
        {
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            int largestIndex = index;


            if (left < maxHeap.Count && maxHeap[left] > maxHeap[largestIndex])
            {
                largestIndex = left;
            }

            if (right < maxHeap.Count && maxHeap[right] > maxHeap[largestIndex])
            {
                largestIndex = right;
            }

            if (largestIndex != index)
            {
                Swap(index, largestIndex);
                index = largestIndex;
            }
            else break;
        }
    }

    public static void Swap(int a, int b)
    {
        (maxHeap[a], maxHeap[b]) = (maxHeap[b], maxHeap[a]);
    }
}

다른 사람의 흥미로운 풀이

코딩테스트 :

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

1 초 (추가 시간 없음) (하단 참고)

128 MB

104250

50307

39680

49.291%

문제

널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.

출력

입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

using System.Collections.Generic;
using System.Text;

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

    public static void Main()
    {
        StringBuilder sb = new StringBuilder();

        int n = int.Parse(Console.ReadLine());

        for (int i = 0; i < n; i++)
        {
            int temp = int.Parse(Console.ReadLine());

            if (temp != 0)
            {
                minHeap.Add(temp);
                int tempIndex = minHeap.Count - 1;

                while (tempIndex > 0)
                {
                    int parent = (tempIndex - 1) / 2;

                    if (minHeap[parent] > temp)
                    {
                        Swap(tempIndex, parent);
                        tempIndex = parent;
                    }
                    else break;
                }
            }
            else 
            {
                if (minHeap.Count != 0)
                {
                    sb.AppendLine(Pop().ToString());
                }
                else sb.AppendLine(0.ToString());
            }
            
        }
        Console.WriteLine(sb.ToString());
    }

    public static int Pop()
    {
        int min = minHeap[0];

        int lastIndex = minHeap.Count - 1;

        minHeap[0] = minHeap[lastIndex];
        minHeap.RemoveAt(lastIndex);

        Heapify();


        return min;
    }

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

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

            int smallest = minIndex;

            if (left < minHeap.Count && minHeap[smallest] > minHeap[left])
            {
                smallest = left;
            }

            if (right < minHeap.Count && minHeap[smallest] > minHeap[right])
            {
                smallest = right;
            }

            if (smallest != minIndex)
            {
                Swap(minIndex, smallest);
                minIndex = smallest;
            }
            else break;
        }

    }

    public static void Swap(int a, int b)
    {
        (minHeap[a], minHeap[b]) = (minHeap[b], minHeap[a]);
    }
}

코딩테스트 : 11286번 절댓값 힙

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

1 초 (추가 시간 없음) (하단 참고)

256 MB

70353

40205

31588

57.180%

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

배열에 정수 x (x ≠ 0)를 넣는다.
배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 절댓값이 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면

using System.Collections.Generic;
using System.Text;

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

    public static void Main()
    {
        StringBuilder sb = new StringBuilder();

        int n = int.Parse(Console.ReadLine());

        for (int i = 0; i < n; i++)
        {
            int temp = int.Parse(Console.ReadLine());

            if (temp != 0)
            {
                minAbsHeap.Add(temp);
                int tempIndex = minAbsHeap.Count - 1;

                while (tempIndex > 0)
                {
                    int parentIndex = (tempIndex - 1) / 2;

                    int currentValue = minAbsHeap[tempIndex];
                    int parentValue = minAbsHeap[parentIndex];

                    if (Math.Abs(parentValue) > Math.Abs(currentValue) ||
                        (Math.Abs(parentValue) == Math.Abs(currentValue) && parentValue > currentValue))
                    {
                        Swap(tempIndex, parentIndex);
                        tempIndex = parentIndex;
                    }
                    else break;
                }

            }
            else
            {
                if (minAbsHeap.Count != 0)
                {
                    sb.AppendLine(Pop().ToString());
                }
                else sb.AppendLine(0.ToString());
            }
        }

        Console.WriteLine(sb.ToString());
    }

    public static int Pop()
    {
        int min = minAbsHeap[0];

        int lastIndex = minAbsHeap.Count - 1;

        minAbsHeap[0] = minAbsHeap[lastIndex];
        minAbsHeap.RemoveAt(lastIndex);

        Heapify();


        return min;
    }

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

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

            int smallest = minIndex;

            if (left < minAbsHeap.Count)
            {
                if (
                    (Math.Abs(minAbsHeap[smallest]) > Math.Abs(minAbsHeap[left])) ||
                    (Math.Abs(minAbsHeap[smallest]) == Math.Abs(minAbsHeap[left]) &&
                     minAbsHeap[smallest] > minAbsHeap[left])
                )
                {
                    smallest = left;
                }
            }


            if (right < minAbsHeap.Count)
            {
                if (
                    (Math.Abs(minAbsHeap[smallest]) > Math.Abs(minAbsHeap[right])) ||
                    (Math.Abs(minAbsHeap[smallest]) == Math.Abs(minAbsHeap[right]) &&
                     minAbsHeap[smallest] > minAbsHeap[right])
                )
                {
                    smallest = right;
                }
            }


            if (smallest != minIndex)
            {
                Swap(minIndex, smallest);
                minIndex = smallest;
            }
            else break;
        }
    }

    public static void Swap(int a, int b)
    {
        (minAbsHeap[a], minAbsHeap[b]) = (minAbsHeap[b], minAbsHeap[a]);
    }
}

기본적인 세 문제를 풀면서 우선순위 큐에 대한 개념을 잡았다.

일반적인 배열인 배열이나 리스트는 데이터를 삽입하고 정렬할 때 모든 요소를 일괄적으로 정렬해야 한다.

이 경우 시간복잡도는 보통 O(n log n)이지만 삽입과 삭제를 반복할 경우 비효율적일 수 있다.

이 문제를 해결하기 위한 우선순위 큐의 아이디어는, 배열/리스트를 선언하고 정렬을 할 때에, 전체 정렬을 해 버리면 너무 많은 성능상의 문제가 발생하니 우리가 가장 먼저 사용할 자료 ( 가장 먼저 Pop되어 나올 자료 ) 의 특징 ( 가장 큰, 가장 작은 등 ) 이 보장되도록 자료들을 정렬하되 모든 자료들을 매 번 정렬하는 것이 아니라, 필요한 순서의 자료들만 ( Left, Right 등의 트리 구조로 ) 비교하며 정렬하는 것이다.

이렇게 하면 모든 순서가 보장되지는 않지만, Pop했을 때 나올 수 있는 자료는 그 자료들 중 원하는 특징이 보장된다.

정렬 기준을 커스터마이징하면서 우선순위를 자유롭게 설정할 수 있다는 점도, 시간 복잡도가 O(log n)이라는 점이 장점이다.

'코딩테스트 > 백준' 카테고리의 다른 글

2696번 중앙값 구하기 (0)	2025.04.24
2075번 N번째 큰 수 (0)	2025.04.22
1300번 K번째 수 (0)	2025.04.17
2805번 나무 자르기, 2110번 공유기 설치 (0)	2025.04.17
1654번 랜선 자르기 (C#) (0)	2025.04.14

현재글11279번 최대 힙, 1927번 최소 힙 , 11286번 절댓값 힙

Cadi

1946번 신입 사원, 1463번 1로 만들기, 코딩테스트, 1260번 dfs와 bfs, 오블완, 2178번 미로 탐색, C#, 스레드, 11724 연결 요소의 개수, 유니티, 티스토리챌린지, 틱택토, 멋쟁이사자처럼, Unity, 부트캠프, 2583번 영역 구하기, 10026번 적록색약, socketio, 2529번 부등호, 동적 계획법,

Today :
Yesterday :

Cadi