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

https://softeer.ai/practice/info.do?idx=1&eid=626&sw_prbl_sbms_sn=178347 

Softeer

---

1. 문제

N개의 회의실, M개의 예약현황이 주어지고 회의실마다 예약이 차지 않은 시간대의 개수와 시간대를 출력한다.

 

2. 풀이

TreeMap, StringBuilder, 이차원배열을 사용한 구현 문제다.

TreeMap

- 이전에는 HashMap을 사용했는데 매번 pq에도 같이 넣어서 정렬한 후 poll한 값을 HashMap의 key로 사용하는 방식으로 오름차순을 구현했다. 하지만 훨씬 유용하게 쓰이는 자료구조 TreeMap이란걸 알게되었다.

- TreeMap은 key값을 자동으로 오름차순 정렬해준다. 따라서 HashMap보다는 성능이 안좋지만 지금 같은 매번 key값 정렬이 필요한 경우엔 효율적이다.

- 그리고 기존의 HashMap과 String에서 TreeMap과 StringBuilder로 바꾸니 실행시간이 3배가 줄었다.

- Map의 형태가 <String, int[][]> 형태인데, value값을 따로 int[][] tmp 에 넣어서 그 tmp의 값을 변경하면 복사된 배열이 변경되는게 맞다.

 

StringBuilder

- StringBuilder는 정수를 append해도 문자열로 바꿔주는가? => O

- append가 String의 + 연산보다 빠른가? => "연산 속도는 비슷하나 메모리가 절약된다."

이게 무슨 말이냐면

1. + 연산 사용하여 문자열을 조합할 때마다 새로운 String 객체를 생성한다. 이 객체는 GC의 수거 대상이 된다.

- +로 String객체 100개 이어붙이면 메모리 100개가 낭비되는 셈.

- 즉, +연산이 많아질 수록 메모리가 낭비되고, 이로 인해 가비지 콜렉션이 자주 발생하여 성능 저하를 유발한다.

 (+연산추가 -> 메모리 낭비 -> GC자주발생 -> 성능저하)

2. StringBuilder는 클래스다. append로 문자열을 조합할 때 String 객체를 새로 생성하지 않으므로 메모리를 절약할 수 있다.

- +연산보다는 StringBuilder를 사용하여 메모리를 절약하자

 

이차원배열

- 기존에는 일차원배열을 만들어서 boolean[] time 이런식으로 예약이찼으면 true 를 넣어주었는데 이렇게 하면 이상하게 30점으로 채점됐다.. 

- tmp[9][2]로 생성하여 시간대마다 [0]은 실제 시작시간(idx+9시간), [1]은 실제 종료시간(idx+9시간)을 넣어줬다.

 

3. 코드

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


public class Main
{

    static int N,M;
    static Map<String, int[][]> reservation = new TreeMap<> ();
    
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        for (int i=0; i<N; i++) {
            int[][] tmp = new int[9][2];
            for (int j= 0; j<9; j++) {
                tmp[j][0] = j+9;      //시작시간
                tmp[j][1] = j+9+1;    //끝시간
            }
            reservation.put(br.readLine(), tmp);
        } 
        for (int j=0; j<M; j++) {
            st = new StringTokenizer(br.readLine());
            String name = st.nextToken();
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            int[][] checked = reservation.get(name); //복사가 아님. 수정하면 원본이 수정된다?
            for (int t = start; t<end; t++) {
                checked[t-9][0] = -1; //예약완료
                checked[t-9][1] = -1; //예약완료
            }
        } //입력 끝
        
        StringBuilder sb = new StringBuilder();
        for (Map.Entry<String, int[][]> entry : reservation.entrySet()) {
            sb.append("Room ").append(entry.getKey()).append(":").append("\n");
            StringBuilder tmpSb = new StringBuilder();

            int[][] checked = entry.getValue();
            int cnt = 0;
            int start = -1;
            int end = -1;
            for (int i = 0; i<9; i++) {
                if (checked[i][0] != -1) {
                    if (start == -1) {
                        start = checked[i][0];
                    }
                } else {
                    if (start != -1) {
                        end = checked[i-1][1];
                    }
                }
                if (start != -1 && end != -1) {
                    tmpSb.append(start==9?"09":start).append("-").append(end).append("\n");
                    start = -1;
                    end = -1;
                    cnt++;
                }
            }

            if (start != -1) {
                cnt++;
                tmpSb.append(start==9? "09":start).append("-").append(18).append("\n");
            }

            if (cnt == 0) {
                sb.append("Not available").append("\n");
            } else {
                sb.append(cnt).append(" available:").append("\n");
                sb.append(tmpSb);
            }
            sb.append("-----").append("\n");
        }
        sb.setLength(sb.length()-6); //길이조절로 마지막줄 -----\n을 자른다.
        System.out.println(sb);
    }
}

 

4. 사담

꾸준히 풀자

TreeMap, StringBuilder 유용하게 사용할 듯하다.