글 읽기 - 자바 시간초과 및 틀렸습니다

ykmvm147 3년 전 0

이중 포문을 쓰게도면 시간초과가 나고

while문을쓰게되면 틀렸다고 나오네요

어느 부분이 틀린지 모르겠습니다...

고수님들 도와주세요~!!

import java.util.*;

public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();//보석의 갯수
        int K = sc.nextInt();//가방의 갯수
        
        int jew [][] = new int[N][2];//보석의 정보 배열
        ArrayList <int[]> arr = new ArrayList<int[]>();//보석정보 배열
        int sum = 0;//최종답
        
        for(int i=0; i < N; i++){//보석 정보 입력
            jew[i][0]= sc.nextInt();
            jew[i][1]= sc.nextInt();
            arr.add(new int[]{jew[i][0],jew[i][1]});   
        }
        
        Arrays.sort(jew, new Comparator<int[]>(){//무게 기준 내림차순
            public int compare(int[] t1, int[] t2){
                return t2[1] - t1[1];
            }
        });
        
        for(int i=0; i<K; i++){
           int bag = sc.nextInt();//가방 정보 받기
           int j=0;
           boolean z = true;
            while(z){//가방정보 받으면 비교하기
                
              if(j <= arr.size()){
                  z = false;
              }
                
             if(bag >= arr.get(j)[0]){
                 sum += arr.get(j)[1];
                 arr.remove(j);
                 z = false;
               }
                
               j++;
                
             }
        }
        
        System.out.println(sum);        
        
    }
}

adxx 3년 전 0

고수는 아니지만 코드의 시간 복잡도가 O(N²)으로 TLE가 당연해 보이네요(정확히는 N*K이고 둘 다 30만쯤 되니...)

이 부분에서 시간을 절약해야 할 것 같아요!

ykmvm147 3년 전 0

비교 for문에서 시간을 줄여야 된다는 소리인가요??

정렬을 무게 를 중심으로 내림차순으로 했는데 다른것을 건들여야하는건가요??

adxx 3년 전 0

O(N) 뒤에 로그하나가 따라오는 정도로 풀면 될 것 같네요

djm03178 3년 전 1

우선 시간 복잡도의 개념을 먼저 공부해보시면 좋을 것 같습니다. 그러면 이 코드가 최악의 경우에 O(NK)가 된다는 것을 계산할 수 있고, 줄이기 위한 아이디어는 어떤 시간 복잡도를 가지게 되는지, 통과하려면 어느 정도의 시간 복잡도가 나와야 할지를 생각해내실 수 있을 것 같습니다.

http://www.secmem.org/blog/202... 를 참고하세요.

adxx 3년 전 0

@djm03178 좋은내용 감사합니다

ykmvm147 3년 전 0

우선순위 큐를 사용하게 되면 시간 초과에 도움이 되나요?

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

문제

문제

출처

ICPC

자바 시간초과 및 틀렸습니다

ykmvm147 3년 전 0

adxx 3년 전 0

ykmvm147 3년 전 0

adxx 3년 전 0

djm03178 3년 전 1

adxx 3년 전 0

ykmvm147 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말