CANADATRIP 정답은 나오는데 시간이 문제인거 같네요 ㅠㅠ

  • zmfldlwl
    zmfldlwl

    import java.util.*;

    public class Main
    {
    static class city
    {
    int start_loc = 0;
    int reach_loc = 0;
    int gap = 0;

    city() {}
    }
    
    public static void main(String[] args) 
    {
        Scanner s = new Scanner(System.in);
    
        int testcase = Integer.parseInt(s.nextLine());
    
        if(testcase < 0 || testcase > 50)
            return;
    
        for(int test = 0 ; test < testcase ; test++)
        {
            int count = 0;
            List<Integer> sign_loc = new ArrayList<Integer>();
            String[] citynum_location = s.nextLine().split(" ");
    
            int citynum = Integer.parseInt(citynum_location[0]);
            if(citynum < 1 || citynum > 5000) return;
    
            int location = Integer.parseInt(citynum_location[1]);
            if(location < 1 || location > (Math.pow(2,31) -1)) return;
    
            String[] value = new String[citynum];
            city[] temp = new city[citynum];
    
            for(int i=0;i<citynum;i++)
            {
                value = s.nextLine().split(" ");
                temp[i] = new city();
                temp[i].reach_loc = Integer.parseInt(value[0]);
                temp[i].start_loc = Integer.parseInt(value[1]);
                temp[i].gap = Integer.parseInt(value[2]);
                if(temp[i].reach_loc < 1 || temp[i].reach_loc > 8030000 || temp[i].start_loc < 1 || temp[i].start_loc > 8030000 
                        || temp[i].gap < 1 || temp[i].gap > 8030000) return;
            }
            //입력완료
            for(int i=0;i<citynum;i++)
            {
                int current = temp[i].reach_loc - temp[i].start_loc;
                while(current <= temp[i].reach_loc)
                {
                    sign_loc.add(current);
                    current += temp[i].gap;
                }       
            }
    
            sign_loc.sort(null);
    
            System.out.println(sign_loc.get(location-1));
        }
    }

    }

    예제 입력햇을때 정답은 나오고 과정은 맞는것같은데 메모리와 속도가 문제인거 같네요... sign_loc.sort()부분에서 엄청난 시간을 잡아먹는것 같고 메모리도 잡아 먹는것 같구요... 어떤 부분을 수정해야 맞을까요? ㅠㅠ


    5년 전
2개의 댓글이 있습니다.
  • Being
    Being

    표지판의 수는 매우 많기 때문에, 모든 표지판을 생성하고 정렬하는 것으로는 문제를 해결하실 수 없습니다. 만약 G_i가 모두 1이더라도 올바른 답을 내어야 합니다.


    5년 전 link
  • Being
    Being

    아울러 다음부터는 다른 질문과 답변 게시판의 게시글과 글 작성시에 표시되는 도움말을 참조하시어 소스 코드가 구문 강조될 수 있도록 해 주시기 바랍니다.


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