[SW Expert Academy] 9280 진용이네 주차타워 [Java]

[ 시간복잡도 ]

[ 핵심풀이 ] : 아래 소스코드기준

-차가 들어올 때 (type>0)
1) 주차공간이 남아있는지 확인한다 → park

2) 주차가 가능하다면 맨 첫번째 주차공간부터 주차한다

3) 주차시 주차중인 차갯수(park), 주차공간(visit), 차량이 주차한공간(parking), 지불해야할 요금(car*pay) 값들을 변경

4) 만약 주차공간이 남아있지않다면, 그차는 대기시킨다 (q)

-차가 나갈 때 (type>0)

1) 주차중인 차갯수(park), 주차공간(visit), 차량이 주차한공간(parking) 값들을 변경

2) 한 자리가비었으므로 대기중인 차가 있다면 주차시작 (park, q)

3) 차가 들어올 때의 경우와 똑같이 진행.

[ 핵심소스 ]

문제를 읽다 명령어 개수에대해 파악하지 못하여 while(ture){ if-break }로 구사했더니 런타임에러가 났었다.

다행히 찾아서 문제조건에맞게 진행했을 때, 정상적으로 pass가 나왔다

for(int d=0;d<2*M;d++)

[ Java ]

import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Solution {
    static int result;

    static void init(Scanner sc) throws NumberFormatException, IOException {
        int N = sc.nextInt();
        int M = sc.nextInt();

        boolean visit[] = new boolean[N + 1];
        int parking[] = new int[M + 1]; 

        int pay[] = new int[N + 1];
        int car[] = new int[M + 1];

        for (int i = 1; i <= N; i++)
            pay[i] = sc.nextInt();
        for (int i = 1; i <= M; i++)
            car[i] = sc.nextInt();
		
        Arrays.fill(parking, 0);
        Arrays.fill(visit, false);
        solve(N, M, visit, parking, pay, car, sc);
    }

    static void solve(int N, int M, boolean visit[], int parking[], int pay[], int car[], Scanner sc) {
        Queue<Integer> q = new LinkedList<Integer>();

        int park = 0;
        for(int d=0;d<2*M;d++){
            int type = sc.nextInt();
            if (type > 0) {
                if (park != N) {
                    for (int i = 1; i <= N; i++) {
                        if (!visit[i]) {		
                            park++;			
                            visit[i] = true;
                            parking[type] = i;
                            result += car[type] * pay[i];
                            break;
                        }
                    }
                }
                else
					q.add(type);
            } else {
                type = Math.abs(type);
                park--;
                visit[parking[type]]=false;
                parking[type] = 0;
            }
            while (park != N && !q.isEmpty()) {
                int input = q.poll();
                for (int i = 1; i <= N; i++) {
                    if (!visit[i]) {
                        visit[i] = true;
                        parking[input]=i;
                        result += car[input] * pay[i];
					}
                }
                park++;
            }
        }
    }

	public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            result = 0;
            init(sc);
            System.out.println("#" + t + " " + result);
        }
    }
}