[softeer] 6266

문제

 

 

 

제약조건

 

 

메모리 제약

 

입/출력

 

문제 분석

원래는 각 시간마다 배열을 쪼개서 풀 생각을 했었다. 그러다보니 상태가 너무 꼬이게 되어서 각 숫자마가 기준을 두기로 하였다.

0 : 사용가능
1 : 사용시작
2 : 사용종료
3 : 사용중(선택불가)

각 시간별 상태를 두고 생각을 해보면 아래와같이 나오게 된다.

1. 시작은 0, 2만 가능하다.
2. 종료는 1, 배열의 종료가 가능하다.


그렇다면 아래와같은 흐름으로 코드를 작성하면 될 것 같다.
1. 방이름 : [시간에 따른 상태 배열]
2. 예약 목록에 따라서 방 상태 변경
3. 위에 나온 상태값으로 사용가능 방 조회

 

 

풀이 1

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

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

        /*
            * 테스트
            * 9 10 11 12 13 14 15 16 17 18
            * 0  1  2  0  0  1  3  2  0  0
            *
            * 0,2 => 1을 찾을때까지 진행 (끝이면 종료)
            *
         */

        String[] inputs = bf.readLine().split(" ");

        int roomCnt = Integer.parseInt(inputs[0]); // 방 개수
        int reservCnt = Integer.parseInt(inputs[1]); // 예약 개수

        // 방이름 : [예약시간]
        HashMap<string, int[]=""> roomsAllInfo = new HashMap<>();

        // 방 이름 입력
        for (int i = 0; i < roomCnt; i++) {
            // 예약 시간 처리 목록
            int[] rooms = new int[10];
            // 예약시간 0으로 초기화
            for (int j = 0; j < 10; j++) {
                rooms[j] = 0;
            }
            roomsAllInfo.put(bf.readLine(), rooms);
        }
        
        // 예약 등록
        for (int i = 0; i < reservCnt; i++) {
            String[] reservNames = bf.readLine().split(" ");
            // 예약된 방 시간 가져오기
            int[] reservedRooms = roomsAllInfo.get(reservNames[0]);

            int start = Integer.parseInt(reservNames[1])-9;
            int end = Integer.parseInt(reservNames[2])-9;
            reservedRooms[start] = 1;
            reservedRooms[end] = 2;
            for (int j = start+1; j < end; j++) {
                reservedRooms[j] = 3;
            }
        }

        // 정렬
        List keySet = new ArrayList<>(roomsAllInfo.keySet());
        Collections.sort(keySet);

        for (String key : keySet) {
            int[] reservedRooms = roomsAllInfo.get(key); // 예약된 방 가져오기
            List<string[]> avaiableRooms = new ArrayList<>();
            String[] avaiableTimes = new String[2];
            boolean findTime = false; // 찾을 값 false: 시작, true: 종료

            // 시작 위치 찾기
            for (int i = 0; i < reservedRooms.length; i++) {
                if (!findTime) { // 시작시간 찾기
                    if (reservedRooms[i] == 0 || reservedRooms[i] == 2) {
                        avaiableTimes[0] = String.format("%02d", i+9);
                        findTime = !findTime;
                    }
                } else { // 종료시간 찾기
                    if (reservedRooms[i] == 1 || i == reservedRooms.length-1) {
                        avaiableTimes[1] = String.format("%02d", i+9);
                        findTime = !findTime;
                        avaiableRooms.add(avaiableTimes);
                        avaiableTimes = new String[2];
                    } else if (reservedRooms[i] == 3) {
                        avaiableTimes = new String[2];
                        findTime = !findTime;
                        continue;
                    }
                }
            }

            System.out.printf("Room %s:\r\n",key);
            System.out.println(avaiableRooms.size() == 0 ? "Not available" : avaiableRooms.size()+" available:");
            for (int i = 0; i < avaiableRooms.size(); i++) {
                System.out.println(avaiableRooms.get(i)[0] + "-"+avaiableRooms.get(i)[1]);
            }

            if (!key.equals(keySet.get(keySet.size()-1))) {
                System.out.println("-----");
            }
        }

    }
}

 

 

실패

결과를 봤는데 생각보다 많은 오답이 있었다...
뭔가 이상해서 로직을 한번 더 생각해보기로 하였다. 그러다가 반례를 찾았다.

1. 11-12
예약
9 10 11 12 13 14 15 16 17 18
0   1   2   0   0   0   0   0   0   0\

2. 10-11 예약
9 10 11 12 13 14 15 16 17 18
0   1   2   2   0   0   0   0   0   0

이렇게되면 11시에 다시 시작으로 값을 인식해버리고 case가 너무 많이 늘어나게된다.

만약에 시간이 이어지면 3 예약불가 상태로 변경하도록 로직을 수정하였다.

 

 

풀이1

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

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

        String[] inputs = bf.readLine().split(" ");

        int roomCnt = Integer.parseInt(inputs[0]); // 방 개수
        int reservCnt = Integer.parseInt(inputs[1]); // 예약 개수

        // 방이름 : [예약시간]
        HashMap<string, int[]=""> roomsAllInfo = new HashMap<>();

        // 방 이름 입력
        for (int i = 0; i < roomCnt; i++) {
            // 예약 시간 처리 목록
            int[] rooms = new int[10];
            // 예약시간 0으로 초기화
            for (int j = 0; j < 10; j++) {
                rooms[j] = 0;
            }
            roomsAllInfo.put(bf.readLine(), rooms);
        }

        // 예약 등록
        for (int i = 0; i < reservCnt; i++) {
            String[] reservNames = bf.readLine().split(" ");
            // 예약된 방 시간 가져오기
            int[] reservedRooms = roomsAllInfo.get(reservNames[0]);

            int start = Integer.parseInt(reservNames[1])-9;
            int end = Integer.parseInt(reservNames[2])-9;
            reservedRooms[start] = reservedRooms[start] == 2 ? 3 : 1;
            reservedRooms[end] = reservedRooms[end] == 1 ? 3 : 2;
            for (int j = start+1; j < end; j++) {
                reservedRooms[j] = 3;
            }
        }

        // 정렬
        List keySet = new ArrayList<>(roomsAllInfo.keySet());
        Collections.sort(keySet);

        for (String key : keySet) {
            int[] reservedRooms = roomsAllInfo.get(key); // 예약된 방 가져오기
            List<String[]> avaiableRooms = new ArrayList<>();
            String[] avaiableTimes = new String[2];
            boolean findTime = false; // 찾을 값 false: 시작, true: 종료

            for (int i = 0; i < reservedRooms.length; i++) {
                if (!findTime) { // 시작 위치 찾기
                    if (reservedRooms[i] == 0 || reservedRooms[i] == 2) {
                        avaiableTimes[0] = String.format("%02d", i+9);
                        findTime = !findTime;
                    }
                } else { // 종료 위치 찾기 (1이거나, 끝이거나)
                    if (reservedRooms[i] == 1 || i == reservedRooms.length-1) {
                        avaiableTimes[1] = String.format("%02d", i+9);
                        findTime = !findTime;
                        avaiableRooms.add(avaiableTimes);
                        avaiableTimes = new String[2];
                    }
                }
            }

            System.out.printf("Room %s:\r\n",key);
            System.out.println(avaiableRooms.size() == 0 ? "Not available" : avaiableRooms.size()+" available:");
            for (int i = 0; i < avaiableRooms.size(); i++) {
                System.out.println(avaiableRooms.get(i)[0] + "-"+avaiableRooms.get(i)[1]);
            }

            if (!key.equals(keySet.get(keySet.size()-1))) {
                System.out.println("-----");
            }
        }
    }
}

 

 

성공

 

 

링크

https://softeer.ai/practice/6266

Softeer - 현대자동차그룹 SW인재확보플랫폼