SWEA[9280] - 진용이네 주차타워[D3]

링크

SWEA[9280]

문제설명

• 시뮬레이션

문제풀이

• 시뮬레이션

문제코드

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

public class Solution9280_1 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/swea/9280.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine().trim());

        for (int test_case = 1; test_case <= T; test_case++) {
            int ans = 0;
//            입력
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int n = Integer.parseInt(st.nextToken());  
            int m = Integer.parseInt(st.nextToken());
            int[] R = new int[n];
            int[] park = new int[n];
            int[] W = new int[m + 1];
            LinkedList<Integer> move = new LinkedList<>();
            LinkedList<Integer> wait = new LinkedList<>();

            for (int i = 0; i < n; i++) {
                R[i] = Integer.parseInt(br.readLine());
            }

            for (int i = 1; i <= m; i++) {
                W[i] = Integer.parseInt(br.readLine());
            }

            for (int i = 0; i < 2 * m; i++) {
                move.add(Integer.parseInt(br.readLine()));
            }

            int now = 0;
            int front = 0;
            while (!move.isEmpty()) {
                now = move.poll();
                if (now > 0) {    //차 대는 명령
//                    대기열 우선고려
                    wait.add(now);
                    front = wait.peek();
//                    차 대는거 시작
                    for (int i = 0; i < n; i++) {
                        if (park[i] == 0) { // 주차장이 비어있으면
                            park[i] = front; // 차 대고
                            ans += R[i] * W[front]; // 주차비용
                            wait.poll();
                            break;
                        }
                    }
//                    주차장 셋 다 차있는 경우
//                    계속 대기
//                    if(!parked) {
////                    대기중- 아무것도 안함
//                    }
                }
                else {    //차 빼는 명령
                    now = -now;    //음수 양수로 바꿈
                    for (int i = 0; i < n; i++) {
                        if (park[i] == now) { // 주차장에 그 차를 찾음
                            park[i] = 0; // 차 빼고
                            if(!wait.isEmpty()) {    //대기중인 차 있으면 바로 거기에 주차시킴
                                now = wait.poll();
                                park[i] = now;
                                ans += R[i] * W[now];
                            }
                            break;
                        }
                    }
                }
            }

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

아쉬운점

• W 인덱싱 +1씩 하므로, 입력도 +1씩해서 받아야함.
• Linkedlist 시간초과
  • 차를 못 넣을 때, 다음 차 빼는거까지 탐색하는 알고리즘이 시간초과의 원인이었음.
    • 처음에 다 차넣고, 나중에 다 차빼는 경우 m^2 만큼 탐색해서 시간이 오래 걸림
  • Linkedlist를 하나 더 만들어서 대기 list 생성하여 계산

잘한점

• 딱히