[Baekjoon] 8978_VLAK

문제(출처: https://www.acmicpc.net/problem/8978)

---

< VLAK >

 

문제 풀이 

 

1. 아직 자리가 남아있는 객차들 중 자신의 이름과 같은 첫 글자를 가진 승객이 가장 적은 객차를 고른다.
2. 그런 객차가 여러 개라면, 전체 승객 수가 가장 적은 객차를 고른다.
3. 그래도 여러 개라면, 가장 앞에 있는 객차를 선택한다.

 

my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.StringTokenizer;
import java.io.InputStreamReader;

public class _8978_ { // VLAK

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int arr[] = new int[n];
		HashMap<Integer, HashMap<Character, Integer>> map = new HashMap<>();

		for (int i = 0; i < n; i++) {
			map.put(i, new HashMap<>());
		}

		int p = Integer.parseInt(bf.readLine());

		for (int i = 0; i < p; i++) {
			char name = bf.readLine().charAt(0);
			int idx = -1, cnt = 0, sum = 0;

			for (int j = 0; j < n; j++) {
				if (arr[j] == k) {
					continue;
				}
				if (idx == -1) {
					idx = j;
					if (map.get(idx).containsKey(name)) {
						cnt = map.get(idx).get(name);
					}
					sum = arr[idx];
				} else {
					if (map.get(j).containsKey(name)) {
						if (cnt > map.get(j).get(name) || (cnt == map.get(j).get(name) && sum > arr[j])) {
							idx = j;
							sum = arr[j];
							cnt = map.get(j).get(name);
						}
					} else {
						if (cnt > 0 || (cnt == 0 && sum > arr[j])) {
							idx = j;
							sum = arr[j];
							cnt = 0;
						}
					}
				}

			}
			arr[idx] += 1;
			if (map.get(idx).containsKey(name)) {
				map.get(idx).put(name, map.get(idx).get(name) + 1);
			} else {
				map.get(idx).put(name, 1);
			}
		}

		for (int i = 0; i < n; i++) {
			bw.write(arr[i] + " ");
		}
		bw.flush();
	}
}

변수)
n, k : 객차 수, 각 객차의 정원
arr : 각 객차에 탑승한 승객 수
map : 각 객차에 탑승한 승객의 이름 첫 글자와 그 승객 수
p : 탑승하려는 승객 수
name : 승객 이름 첫 글자
idx, cnt, sum : 객차 번호, 그 객차에 있는 승객의 이름 첫 글자 승객 수, 그 객차에 탑승한 승객 수

 

객차 수와 각 객차의 정원을 입력받는다. 탑승하려는 승객 수를 입력받아 그 수만큼 다음 과정을 반복한다.

 

1) 객차에 정원이 다 찼다면 다음 객차를 살펴본다.

2) 객차에 정원이 다 차지 않았다면 idx와 cnt, sum을 초기화한다.

3) 객차에 그 승객의 첫 글자를 가진 승객이 있다면 -> 현재 값보다 적은 객차인지 확인하고 적은 객차라면 값을 업데이트한다. 또한, 현재 값과 같은 값을 가진 객차라면 전체 승객 수를 비교해 적은 값으로 업데이트한다.

4) 객차에 그 승객의 첫 글자를 가진 승객이 없다면 -> 현재 값보다 적은 객차인지 확인하고 적은 객차라면 값을 업데이트한다. 또한, 현재 값과 같은 값을 가진 객차라면 전체 승객 수를 비교해 적은 값으로 업데이트한다.

5) 최종 구한 객차에 값을 추가한다.

 

최종 arr의 값을 출력한다.

---

---