글 읽기 - 문제 예외상황이 있어서요.

powerlsj7 2년 전 0

밑에 while (current * 2 + 2 < q.Count) 이부분이

우선수위 큐 pop할때 자식 탐색하는 조건인데 저 조건대로 해도 채점 통과합니당.

저 코드를 가지고 다음 문제인 가운데를 말해요를 풀면 저 조건이 틀려서 틀립니다로 나옵니다.

저 조건이 잘못된 이유는 자식이 좌측 우측 2개일때만 들어오게 되어서 왼쪽자식만 있는 경우 무시하기 때문에 큐가 2개면 정렬을 안해버려서 최대값이나 최소값이 안나오거든요.

덕분에 우선순위 큐는 제대로 공부한 것 같습니다. 감사합니다 ㅎㅎ;;

using System;
using System.IO;
using System.Collections.Generic;
namespace ThisIsCShaps
{
    class myPriorityQueue
    {

        private List<int> q = new List<int>();
        public int count = 0;
        private int temp = 0;
        public void swap(int a, int b)
        {
            temp = q[a];
            q[a] = q[b];
            q[b] = temp;
        }
        public void add(int n)
        {

            count++;
            q.Add(n);
            int idx = q.Count - 1;
            while (idx > 0)
            {
                if (Math.Abs(q[(idx - 1) / 2]) == Math.Abs(q[idx]))
                {
                    //같으면 순수값 비교
                    if (q[(idx - 1) / 2] > q[idx])
                    {
                        swap((idx - 1) / 2, idx);
                        idx = (idx - 1) / 2;
                    }
                    else
                    {
                        break;
                    }
                }
                else if (Math.Abs(q[(idx - 1) / 2]) > Math.Abs(q[idx]))
                {
                    //자식이 더 작으면 절대값부분
                    swap((idx - 1) / 2, idx);
                    idx = (idx - 1) / 2;
                    //스왑해줌
                }
                else
                {
                    break;
                }



                //자식이 부모보다 크다 그럼 바꿔준다.
                //역 정렬

            }

        }

        public int top()
        {

            return q[0];
        }
        public int pop()
        {
            int t = q[0];

            q[0] = q[q.Count - 1];
            q.RemoveAt(q.Count - 1);
            count--;

            int current = 0, child = 0;
           while (current * 2 + 2 < q.Count)////////////////이부분이요
            {
                //부모 우측 자식값이 범위안에들어있는 경우
                child = current * 2 + 1; //왼쪽 자식
                if (child + 1 < q.Count)
                {
                    //왼쪽자식놈이 
                    if (Math.Abs(q[child]) == Math.Abs(q[child + 1]))
                    {
                        //같으면 순수값 비교
                        if (q[child] > q[child + 1])
                        {
                            child++;
                        }

                    }
                    else if(Math.Abs(q[child]) > Math.Abs(q[child + 1]))
                    {
                        child++;
                    }


                }
                if (Math.Abs(q[current]) == Math.Abs(q[child]))
                {
                    if (q[current] < q[child])
                    {
                        break;
                    }
                }
                else if (Math.Abs(q[current]) < Math.Abs(q[child]))
                {
                    break;
                }
                swap(current, child);
                current = child;
            }

            return t;

        }
    }
    class Program
    {
        static StreamReader sr = new StreamReader(Console.OpenStandardInput());
        static StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        static myPriorityQueue pq = new myPriorityQueue();
        static int n;

        static void Main(string[] args)
        {
            n = int.Parse(sr.ReadLine());
            for (int i = 0; i < n; i++)
            {
                int v = int.Parse(sr.ReadLine());
                if (v == 0)
                {
                    if (pq.count > 0)
                    {
                        sw.WriteLine(pq.top());
                        pq.pop();
                    }
                    else
                    {
                        sw.WriteLine(0);
                    }
                }
                else
                {
                    pq.add(v);
                }
            }
            sw.Close();
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 예외상황이 있어서요.

powerlsj7 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말