[Softeer] [21년 재직자 대회 예선] 회의실 예약

문제

링크 : https://softeer.ai/practice/6266

사용 언어 : JAVA

---

---

내 생각

초기 생각

처음에는 HashMap<String:회의실 명, boolean[]: 시간테이블>를 만들어서 회의 시간마다 true로 체크하고, 출력할 때 다시 계산하는 방식을 사용하려 했다. 그런데 회의실이 빈 start시간, end시간을 일일이 구하는게 너무 귀찮아서 다른 방식을 생각했다.

 

개선

회의가 (9-10), (12-13), (16-17) 이렇게 있다면, 회의실이 비어있는 시간대는 (10-12), (13-16), (17-18) 이렇게 된다.

 

아래의 (1)처럼 주어진 회의 시작/종료 쌍을 (2)처럼 변경하여 새로운 쌍을 짓는 것이다.

(1)     (회의1 시작, 회의1 종료)  /  (회의2 시작, 회의2 종료)  /  ...  /  (회의N 시작, 회의N 종료) 
(2)     (9, 회의1 시작)  /  (회의1 종료, 회의2 시작)  /  ...  /  (회의N 종료, 18)

그래서 큐나 스택에다가 9를 먼저 넣은 후, 회의들의 시작/종료 시간을 모두 삽입한 뒤 마지막으로 18을 삽입한다.

 

단 서로 다른 회의의 종료/시작 시간이 겹치는 경우 == 연달아서 회의실을 사용하는 경우이기 때문에 리스트에서 각 회의들의 종료/시작 시간을 빼줘야 한다. 이는 9시, 18시에도 동일하게 적용되며 만약 첫번째 회의가 9시에 시작하거나 마지막 회의가 18시에 끝난다면 9, 18을 리스트에서 빼준다.

 

 

이를 구현하기 위해 아래와 같은 자료구조를 사용하였다.

• TreeMap <String:회의실 명, PriorityQueue<int[]>: 회의 시간 쌍>
• Deque <Integer:시간>

TreeMap은 회의실 명을 알파벳 순으로 정렬하기 위해 사용하였고,

Deque는 1) 회의시간 쌍을 지을때 뒤에서 입력/삭제해야 함, 2) 출력할 때 앞에서부터 뽑아 써야함 의 이유로 사용하였다.

 

최종 코드

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

public class Main {
  
    public static void main(String[] args) throws IOException {

      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      StringTokenizer tokenizer = new StringTokenizer(br.readLine());

      int N = Integer.parseInt(tokenizer.nextToken());
      int M = Integer.parseInt(tokenizer.nextToken());

      // 회의실 init
      Map<String, PriorityQueue<int[]>> rooms = new TreeMap<>();
      for(int i=0; i<N; i++) {
        rooms.put(br.readLine(), new PriorityQueue<>((o1, o2) -> o1[0]-o2[0]));
      }

      // 회의 표시
      for(int i=0; i<M; i++) {
        tokenizer = new StringTokenizer(br.readLine());
        
        String room = tokenizer.nextToken();
        int st = Integer.parseInt(tokenizer.nextToken());
        int et = Integer.parseInt(tokenizer.nextToken());

        rooms.get(room).add(new int[]{st, et});
      }

      StringBuilder sb = new StringBuilder();
      
      // 각 회의실별 예약된 시간들
      for(Map.Entry<String, PriorityQueue<int[]>> entry : rooms.entrySet()) {
        String room = entry.getKey();
        PriorityQueue<int[]> pq = entry.getValue();

        Deque<Integer> dq = new ArrayDeque<>();
        dq.add(9);
        
        // 만약 바로 dq의 last(== 지난 회의의 종료시간)가 현재 회의의 시작시간과
        // 같을 경우, 둘 다 삭제 후 종료 시간만 삽입
        // 다를 경우, 시작/종료 둘 다 삽입
        while(!pq.isEmpty()) {
          int[] temp = pq.poll();
          if (dq.getLast() == temp[0]) {
            dq.pollLast();
          } else {
            dq.add(temp[0]);
          }
          dq.add(temp[1]);
        }
        
        // 마지막 회의의 종료 시간이 18시라면 삭제, 아니면 18시 삽입
        if (dq.getLast() == 18) {
          dq.pollLast();
        } else {
          dq.add(18);
        }

        sb.append("Room ").append(room).append(":\n");
        
        if(dq.size() == 0) {
          sb.append("Not available\n");
        }
        else {
          sb.append(dq.size()/2).append(" available:\n");
          
          // dq에 담긴 시간 차례로 2개씩 뽑아서 출력
          while(!dq.isEmpty()) {
            String s = dq.poll() + "";
            String e = dq.poll() + "";
            sb.append(s.equals("9")?"09":s).append("-").append(e).append("\n");
          }
        }
        
        sb.append("-----\n");
      }

      sb.setLength(sb.length() - 6);
      System.out.println(sb);
    }
}

---

느낀점

• 자료구조의 중요성