[Softeer]

좌석관리 : https://softeer.ai/practice/info.do?idx=1&eid=625

---

Problem

---

Solve

Map<String, int[]> eatPos를 사용하여 현재 먹고 있는 사원의 위치를 저장합니다.
boolean[] isAlreadyEat을 사용하여 이미 먹은 사원을 확인합니다.
int[][] restaurant를 사용하여 각 위치에 먹고있는 사원을 표시합니다.

이 세가지를 이용하여 Q개의 작업을 처리할 수 있습니다.

먼저 In작업이 들어온 경우

• 먹고있는 경우(eatPos.containsKey(id))
• 이미 먹은 경우(isAlreadyEat(id))
• 자리가 없는 경우
• 자리가 있는 경우

를 판단해줍니다.

자리가 가득차있는지 여부는 해당 사원이 앉을 수 있는 자리 위치가 존재하지 않는다면 식당의 자리는 가득차있는것입니다.
앉을 수 있는 위치가 존재한다면 해당 자리에 앉아서 eatPos와 restaurant에 저장해줍니다.

해당 사원이 앉을 수 있는 위치를 반환은 아래와 같습니다.

• 식당에 식사하고 있는 사람이 없다면 (1,1)의 위치를 반환합니다.
• 다른 사람이 식사를 하고 있다면 다른 위치에서 안전도를 각각 비교합니다.
  • 특정 위치에서 다른 사람이 식사하고 있는 위치의 안전도 중 가장 작은값들 중 가장 큰 값을 반환해야합니다.
  • D(X,Y) : 특정 위치에서 다른 사람이 식사하고 있는 위치의 안전도(가장 작은 값)
    • Math.sqrt(Math.pow([다른사람의 식사 위치X]-[특정 위치X],2)+Math.pow([다른사람의 식사 위치Y]-[특정 위치Y],2))
  • 특정 위치의 D(X,Y)에서 가장 큰값이 해당 사원이 식당에 앉을 수 있는 위치입니다.
• 그리고 해당 위치에서 상,하,좌,우에는 다른 사람이 앉아있을 수 없습니다.

식사를 할 수 있는 자리가 생긴 경우 eatPos에 사원 id를 key로 하여 반환받은 위치를 저장하고 restaurant의 반환받은 위치에 사원 id를 갱신합니다.

Out작업이 들어온 경우는

• 먹고있는 경우(eatPos.containsKey(id))
• 아직 먹지않은 경우(!isAlreadyEat[id])
• 이미 먹은 경우

먹고있는 경우에는 eatPos에서 id를 삭제하고 isAlreadyEat[id] = false로 반환하고, restaurant 위치의 id를 0으로 갱신해줍니다.

이를 반복하여 결과를 반환해줍니다.

---

Code

import java.util.*;
import java.io.*;

public class 좌석관리 {
	static int N;
	static int M;
	static int[][] restaurant;
	static Map<Integer, int[]> eatPos;
	static boolean[] isAlreadyEat;

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		int Q = Integer.parseInt(st.nextToken());

		restaurant = new int[N + 1][M + 1];
		eatPos = new HashMap<>();
		isAlreadyEat = new boolean[10001];
		// PriorityQueue<Seat> restaurant = initRestaurant(N, M);

		StringBuilder sb = new StringBuilder();
		while (Q-- > 0) {
			st = new StringTokenizer(br.readLine(), " ");
			String work = st.nextToken();
			int id = Integer.parseInt(st.nextToken());

			if (work.equals("In")) {
				//먹고있음
				if (eatPos.containsKey(id)) {
					sb.append(String.valueOf(id)).append(" already seated.");
				}
				//이미 먹음
				else if (isAlreadyEat[id]) {
					sb.append(String.valueOf(id)).append(" already ate lunch.");
				} else {
					int[] seat = getPos();
					//자리가 없음
					if (seat[0] == 0 && seat[1] == 0) {
						sb.append("There are no more seats.");
					}
					//자리 있음
					else {
						eatPos.put(id, new int[] {seat[0], seat[1]});
						restaurant[seat[0]][seat[1]] = id;
						sb.append(String.valueOf(id))
							.append(" gets the seat (")
							.append(seat[0])
							.append(", ")
							.append(seat[1])
							.append(").");
					}
				}
			} else {
				//먹고 있음
				if (eatPos.containsKey(id)) {
					int[] seat = eatPos.get(id);

					restaurant[seat[0]][seat[1]] = 0;
					eatPos.remove(id);
					isAlreadyEat[id] = true;

					sb.append(String.valueOf(id))
						.append(" leaves from the seat (")
						.append(seat[0])
						.append(", ")
						.append(seat[1])
						.append(").");
				}
				//아직 안먹음
				else if (!isAlreadyEat[id]) {
					sb.append(String.valueOf(id)).append(" didn't eat lunch.");
				}
				//이미 먹음
				else
					sb.append(String.valueOf(id)).append(" already left seat.");
			}
			sb.append("\n");
		}

		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	//사원이 먹을 수 있는 식당 위치
    //먹을수있는 위치가 없다면 초깃값 (0,0) 반환
	static int[] getPos() {

		if (eatPos.isEmpty())
			return new int[] {1, 1};
		int maxY = 0;
		int maxX = 0;
		double maxD = 0;

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				int minX = 0;
				int minY = 0;
				double minD = Double.MAX_VALUE;
				if (restaurant[i][j] != 0 || !distanceGap(i, j))
					continue;
				for (int id : eatPos.keySet()) {
					int[] pos = eatPos.get(id);

					double d = Math.sqrt(Math.pow(pos[0]-i,2)+Math.pow(pos[1]-j,2));

					if (minD > d) {
						minX = i;
						minY = j;
						minD = d;
					}

				}

				//해당 위치에서의 안전도가 다른 위치에서의 안전도보다 높고
                //해당 위치에서의 안전도가 초깃값이 아닌 경우
				if (minD != Double.MAX_VALUE && maxD < minD) {
					maxX = minX;
					maxY = minY;
					maxD = minD;
				}
			}
		}

		return new int[] {maxX, maxY};
	}

	//상,하,좌,우 다른 사람이 식사하는지 여부
	static boolean distanceGap(int x, int y) {
		if (x - 1 > 0 && restaurant[x - 1][y] != 0)
			return false;
		if (x + 1 <= N && restaurant[x + 1][y] != 0)
			return false;
		if (y - 1 > 0 && restaurant[x][y - 1] != 0)
			return false;
		if (y + 1 <= M && restaurant[x][y + 1] != 0)
			return false;

		return true;
	}
}

---

Result

시간을 가장 많이 보냈던 부분이 사원이 식사할 수 있는 위치를 찾기 위해 안전도를 구하는 부분이였습니다.
안전도 조건에 식사를 하고 있는 K개의 위치에서 앉으려고 하는 특정 위치(X,Y)에 대한 최소값이 안전도임을 나타내는 공식임에도 불구하고 특정 위치(X,Y)를 기준으로 식사하고 있는 K개의 위치에 대한 최소값을 구해서 자꾸 다른 엉뚱한 위치가 반환되었습니다.

또 실수했던 부분이, 시간초과가 자꾸 발생하였는데 식사를 할 수있는 위치를 찾기 위해 특정 위치를 선택하였을때, 이미 다른 사람이 앉아있는 자리인지 해당 위치의 상,하,좌,우에 다른 사람이 있는지를 확인하는 조건을 이미 식사하고 있는 K개의 위치를 모두 확인 한 후 걸어주었기 때문에 오래걸렸습니다.

---

Reference