글 읽기 - 병합정렬 런타임 오류 질문

get1ucky 6년 전 0

병합정렬을 사용하는데 자꾸 런타임 오류가 발생합니다.

구현은 단일 연결리스트에서 필요한 부분만 구현해 병합정렬 알고리즘에 썻습니다.

소스를 테스트한 환경은 비주얼 스튜디오에서 테스트했고 동작까지 잘됩니다.

뭐가 문제일까요?

using System;

namespace ConsoleApplication3
{
    class Program
    {
        static void Main(string[] args)
        {
            int k =Convert.ToInt16(Console.ReadLine());
            LinkedList temp = new LinkedList();
            for (int i = 0; i <k ; i++)
                temp.addfirst(Convert.ToInt16(Console.ReadLine()));//입력을 다받음

            temp=mergeSort(temp);
            for (int i = 0; i < k; i++)
                Console.WriteLine(temp.removefirst());
        }
        static LinkedList mergeSort(LinkedList arr)//만약 9 8 65 23 3 4
        {
            LinkedList arr1 = new LinkedList();
            LinkedList arr2 = new LinkedList();
            int N = arr.sizeOf();
            int k = arr.sizeOf() / 2;

            if (N > 2)//최소 3개 이상의 노드가 있을 것  
            {
                for (int i = 0;i<k; i++)  
                    arr1.addlast(arr.removefirst());
                for(int i=0; i<N-k;i++)//5
                    arr2.addlast(arr.removefirst());

                arr1 =mergeSort(arr1);
                arr2=mergeSort(arr2);
            }
            else//arr가 2개 노드가 있을 것  
            {
                for (int i = 0; i < k; i++)  // 만약 9라면 4.5 -> 4
                    arr1.addlast(arr.removefirst());
                for (int i = 0; i < N-k; i++)//5
                    arr2.addlast(arr.removefirst());
            }
            return merge(arr1, arr2);//합병작업
        }
        static LinkedList merge(LinkedList arr1, LinkedList arr2)
        {
            LinkedList arr= new LinkedList();

            while (arr1.sizeOf() > 0 && arr2.sizeOf() > 0)//둘중 하나가 0이 되면 빠져나감
            {
                if (arr1.firstData() < arr2.firstData())
                {
                    arr.addlast(arr1.removefirst());
                }
                else if (arr1.firstData() >= arr2.firstData())
                {
                    arr.addlast(arr2.removefirst());
                }
            }
            if (arr1.sizeOf() > 0)//arr1이 비어있지 않으면
            {
                while(arr1.sizeOf()!=0)
                {
                    arr.addlast(arr1.removefirst());
                }
            }
            else if (arr2.sizeOf() > 0)//arr2이 비어있지 않으면
            {
                while(arr2.sizeOf()!=0)
                {
                    arr.addlast(arr2.removefirst());
                }
            }
            
            return arr;
        }
    }
     
    public class LinkedList
    {
        private Node head=null;
        private Node tail=null;
        int size = 0;
        public class Node
        {
            public int data;
            public Node next;

            public Node(int data)
            {
                this.data = data;
                next = null;
            }
        }
        public void addfirst(int data)
        {
            Node temp = head;
            Node newNode = new Node(data);

            head = newNode;
            newNode.next = temp;

            if (size == 0)
            {
                tail = head;
            }
            size++;
        }
        public void addlast(int data)
        {
            if (size == 0)
            {
                addfirst(data);
            }
            else
            {
                Node temp = tail;
                Node newNode = new Node(data);

                temp.next = newNode;
                tail = newNode;

                size++;
            }
        }
        public int removefirst()
        {
            Node temp = head;
            head = temp.next;
           int returnData = temp.data;
            temp = null;
            size--;
            return returnData;
        }
        public int firstData()
        {
            return head.data;
        }
        public int sizeOf()
        {
            return size;
        }
    }
}

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

문제

문제

출처

ICPC

병합정렬 런타임 오류 질문

get1ucky 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말