글 읽기 - [JAVA] Queue를 이용한 합병정렬 어떻게 틀렸나요..???

kimyongcheol 5년 전 0

merge 메소드를 Queue를 이용해서 풀었습니다.

Queue의 맨 앞부분 값을 비교해서 작은것부터 넣고, 한쪽 큐가 비면 나머지 큐를 차례대로 넣었습니다. 문제가 뭘까요? ㅠ

import java.util.*;
public class Main{
    public static void main(String[]args){        
        Scanner sc = new Scanner(System.in);        
        int n = sc.nextInt();        
        int[] arr = new int[n];        
        for(int i=0;i<n;i++)            
            arr[i] = sc.nextInt();        
        mergeSort(arr, 0, arr.length -1);        
        
        for(int i : arr)            
            System.out.println(i);
    }
    
    public static void mergeSort(int[] arr, int left, int right){
        int mid = (left+right)/2;
        if(left >= right)
            return;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    
    public static void merge(int[] arr, int left, int mid, int right){
        //int A = left-mid;
        //int B = mid+1 - right;
        Queue A = new Queue();
        Queue B = new Queue();
        
        for(int i=left;i<=mid;i++)
            A.push(arr[i]);
        for(int i=mid+1; i<=right;i++)
            B.push(arr[i]);
        
        while(  !(A.empty() && B.empty())  ){
            if(A.front() > B.front()){
                arr[left++] = B.pop();
            } else if(A.front() > B.front()){
                arr[left++] = A.pop();
            }else if(A.empty()){
                while(!B.empty())
                    arr[left++] = B.pop();
            }else
                while(!A.empty())
                    arr[left++]=A.pop();
        }
    }
}

class Node {
    int key;
    Node link;
    public Node(int k){ key = k;}
}

class Queue{
    Node front, back;
    int size = 0;
    public Queue(){ front = null; back = null;}
    void push(int x){
        Node ins = new Node(x);
        if(size == 0){
            front = ins;
            back = ins;
        }
        back.link = ins;
        back = ins;
    }
    boolean empty(){
        return (size == 0);
    }
    int pop(){
        int temp = front.key;
        front = front.link;
        return temp;
    }
    int front(){
        return front.key;
    }
}

djm03178 5년 전 0

queue 구현에서 size를 변화시키는 부분이 없으니 empty() 가 항상 true를 리턴합니다.

kimyongcheol 5년 전 0

size 변화시키는 부분을 넣었는데 널포인터 익셉션이 뜨네요..

이 문제를 혼자 해결해보고싶은데 어떤식으로 해결할 수 있나요???

djm03178 5년 전 0

36번째 줄에서 front를 먼저 호출하고 있어 큐가 비어있어도, 즉 front가 null이라도 front.key를 반환하려고 하게 됩니다.

empty를 먼저 검사하거나, 비어있는 상태에서 front가 호출된 경우에 대한 처리를 따로 해야 합니다.

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

문제

문제

출처

ICPC

[JAVA] Queue를 이용한 합병정렬 어떻게 틀렸나요..???

kimyongcheol 5년 전 0

djm03178 5년 전 0

kimyongcheol 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말