LUNCHBOX문제 RTE의 원인에 대해 질문드립니다.

  • imcme
    imcme

    문제링크 : LUNCHBOX

    먹는 시간순서로 내림차순을 하여 정답을 맞춘 문제인데

    RTE의 원인을 알 수 없어서 질문드립니다.

    RTE가 발생한 코드는 도시락 정보를 저장하는 클래스를

    배열에 넣고 Arrays.sort 를 사용해 정렬하는 방법을 사용했습니다.

    배열을 ArrayList로도 바꿔보고 알고리즘도 다시 생각해 보았다가

    배열을 PriorityQueue로 변경하여 실행하니 '정답'이 나왔습니다.

    이 과정에서 배열이나 ArrayList로 코드를 작성하였을때

    왜 RTE가 발생하는지 잘 모르겠습니다.

    배열을 사용한 코드입니다.(RTE발생)

    import java.io.*;
import java.util.*;

public class Main{  
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine().trim());
        while( T-- > 0 ){
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer wt = new StringTokenizer(br.readLine());
            StringTokenizer et = new StringTokenizer(br.readLine());

            Pack pack[] = new Pack[n];
            for(int i = 0; i < n; i++)
                pack[i] = new Pack(wt.nextToken(), et.nextToken());     
            Arrays.sort(pack);

            int ans = 0;
            int totlaWarmTime = 0;
            for(Pack p : pack){
                totlaWarmTime += p.warmTime;
                ans = Math.max(ans, totlaWarmTime + p.eatTime); 
            }

            System.out.println(ans);
        }
    }
}

class Pack implements Comparable<Pack>{
    int warmTime;
    int eatTime;

    public Pack(String warmTime, String eatTime) {
        this.warmTime = Integer.parseInt(warmTime);
        this.eatTime = Integer.parseInt(eatTime);
    }

    //먹는 시간이 긴순
    @Override
    public int compareTo(Pack o) {
        return eatTime < o.eatTime ? 1 : -1;
    }
}

    우선순위큐를 사용한 코드입니다.(정답)

    import java.io.*;
import java.util.*;

public class Main{  
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine().trim());
        while( T-- > 0 ){
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer wt = new StringTokenizer(br.readLine());
            StringTokenizer et = new StringTokenizer(br.readLine());

            PriorityQueue<Pack> pq = new PriorityQueue<Pack>();
            while(wt.hasMoreTokens())
                pq.add(new Pack(wt.nextToken(), et.nextToken()));

            int ans = 0;
            int totlaWarmTime = 0;

            while(!pq.isEmpty()){
                Pack p = pq.poll();
                totlaWarmTime += p.warmTime;
                ans = Math.max(ans, totlaWarmTime + p.eatTime);
            }

            System.out.println(ans);
        }
    }
}

class Pack implements Comparable<Pack>{
    int warmTime;
    int eatTime;

    public Pack(String warmTime, String eatTime) {
        this.warmTime = Integer.parseInt(warmTime);
        this.eatTime = Integer.parseInt(eatTime);
    }

    //먹는 시간이 긴순
    @Override
    public int compareTo(Pack o) {
        return eatTime < o.eatTime ? 1 : -1;
    }
}


    11년 전
7개의 댓글이 있습니다.
  • hyunhwan
    hyunhwan

    Arrays.sort() 사용 할 때 compareTo에 같을 경우 return 0이 빠져서 그런 것 아닌가 싶습니다.


    11년 전 link
  • imcme
    imcme

    LIBe님 말씀대로네요. 감사합니다.
    다른곳에서 return 0 없이 풀었던기억이 있어서 그점은 미처 생각하지 못했네요 ㅎㅎ


    11년 전 link
  • wookayin
    wookayin

    Arrays.sort 및 Comparable 인터페이스의 javadoc을 꼭 확인하세요. 여기에 지정된 조건이 만족하지 않으면 언제든 오동작할 수 있어 주의해야 합니다. Java의 경우는 보통 단일 값에 대해서는 (a).value - (b).value < 0 등으로 처리하면 충분합니다.

    C++ 도 마찬가지로 STL 비교 함수를 짤 때에는 strict weak ordering을 잘 지켜주어야 합니다.


    11년 전 link
  • imcme
    imcme

    wookayin// API를 더 유의깊게 봐야겠네요. 한가지 질문이 compareTo 같은 경우 return 값이 int형이라 (a).value - (b).value < 0로 처리 불가능 하지 않나요?


    11년 전 link
  • Taeyoon_Lee
    Taeyoon_Lee

    wookayin// (a).value - (b).value < 0 이 된다고?? 뭔가 이상한데..?


    11년 전 link
  • wookayin
    wookayin

    으 잘못썼습니당[...] return a.value - b.value; 같은 걸 의미한 거였어요 :)
    (단 오버플로우 안날때..)


    11년 전 link
  • kcm1700
    kcm1700

    그리고 뺄셈하고 0이랑 비교하는거 overflow나 underflow 날 수 있어서 그렇게 하면 좋지 않습니다 ㅠㅠ


    11년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.