SWEA[2477] - 차량 정비소

링크

SWEA[2477]

문제설명

• 빡구현

문제풀이

• queue 이용

문제코드

package swea;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.StringTokenizer;

public class Solution2477 {
    static class Comp implements Comparator<Integer>{
        @Override
        public int compare(Integer o1, Integer o2) {
            // TODO Auto-generated method stub
            return o1-o2;
        }
    }
    public static Comp comp = new Comp();

    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/2477.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T=Integer.parseInt(br.readLine());
        for (int test_case = 1; test_case <= T; test_case++) {
            int ans=0;
            st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            int[][] a = new int[N+1][3];    //{처리시간, time_cnt, 손님번호}
            int[][] b = new int[M+1][3];    //{처리시간, time_cnt, 손님번호}
            int[] t = new int[K+1];

            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= N; i++) {
                a[i][0] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= M; i++) {
                b[i][0] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for (int i = 1; i <= K; i++) {
                t[i] = Integer.parseInt(st.nextToken());
            }

            ArrayList<Integer> ans_a = new ArrayList<Integer>();
            ArrayList<Integer> ans_b = new ArrayList<Integer>();
            LinkedList<Integer> wait_a = new LinkedList<Integer>();
            LinkedList<Integer> wait_b = new LinkedList<Integer>();
            int time = 0;
            int endcnt = 0;
//            종료조건 최후의 손님까지 다 나갔을 때.
            while(endcnt<K) {
//                접수 대기자들 wait_a
                for (int i = 1; i <= K; i++) {
                    if(t[i]==time) {
                        wait_a.add(i);
                    }
                }
//                고객번호 우선으로 정렬 후
                wait_a.sort(comp);
                for (int i = 0; i < wait_a.size(); i++) {
                    for (int j = 1; j <= N; j++) {
//                        j번 접수창이 비어있으면
                        if(a[j][2]==0) {
//                            대기큐에서 접수창으로 손님들어가고
                            a[j][2] = wait_a.pollFirst();
//                            접수창 시간 cnt 시작
                            a[j][1] = a[j][0];
//                            ans
                            if(j==A) {
                                ans_a.add(a[j][2]);
                            }

//                            size, idx 모두 1씩 줄었음.
                            i--;
                            break;
                        }
                    }
                }
                int debug=0;
//                접수창 시간 --
                for (int i = 1; i <= N; i++) {
                    a[i][1]--;
//                    만약 시간이 0이면 끝났기때문에 정비대기로 넘어감
//                    번호낮은 접수창구우선 고려하는중
                    if(a[i][1]==0) {
                        wait_b.add(a[i][2]);
                        a[i][2]=0;
                    }
                }
                debug=0;
                for (int i = 0; i < wait_b.size(); i++) {
                    for (int j = 1; j <= M; j++) {
//                        j번 접수창이 비어있으면
                        if(b[j][2]==0) {
//                            대기큐에서 접수창으로 손님들어가고
                            b[j][2] = wait_b.pollFirst();
//                            접수창 시간 cnt 시작
                            b[j][1] = b[j][0];
//                            ans
                            if(j==B) {
                                ans_b.add(b[j][2]);
                            }
//                            size, idx 모두 1씩 줄었음.
                            i--;
                            break;
                        }
                    }
                }
                debug=0;
//                접수창 시간 --
                for (int i = 1; i <= M; i++) {
                    b[i][1]--;
//                    만약 시간이 0이면 끝남
//                    번호낮은 접수창구우선 고려하는중
                    if(b[i][1]==0) {
                        endcnt++;
                        b[i][2]=0;
                    }
                }

                time++;
            }

//            System.out.println(ans_a);
//            System.out.println(ans_b);
            for (int i = 0; i < ans_a.size(); i++) {
                if(ans_b.contains(ans_a.get(i))) {
                    ans+=ans_a.get(i);
                }

            }

            if(ans==0)ans=-1;

            System.out.println("#"+test_case+" "+ans);
            /*
             * 초기화
             */
            ans=Integer.MIN_VALUE;
        }//end test_case
    }//end main
}

아쉬운점

• {처리시간, time_cnt, 손님번호} 의 자료구조를 생각하는데에 시간좀 걸렸음
• q의 원소를 for 문을 돌면서 처리하는 경우 인덱싱 제대로 못함
  • q.size() remove하면 q.size()가 주는걸 알고 관련 idx를 -- 해 줘야 했는데
  • 하위 for 문의 idx를 --했었음
  • 또한 break를 안하면 없앤 원소에서 계속 창구탐색처리를 하기 때문에 에러뜸 break도 해야함.
• 답 출력조건 제대로 안읽음
  • 답 없으면 ans = -1

잘한점

• O(N)
  • time*q탐색 = 1000*1000 안터짐
• comparator 클래스 만들어서 정렬함
• 그래도 요구사항 하나하나 다 보면서 했음
• 시간 좀 걸리긴 함 (1시간 15분)
• 디버깅 열심히함...
• Ans 체크하기 위해서 Arraylist써서 contains로 처리