Etc/알고리즘
[softeer] 6266
jjuni_96
2024. 7. 25. 22:23
728x90
문제
제약조건
메모리 제약
입/출력
문제 분석
원래는 각 시간마다 배열을 쪼개서 풀 생각을 했었다. 그러다보니 상태가 너무 꼬이게 되어서 각 숫자마가 기준을 두기로 하였다.
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인재확보플랫폼
softeer.ai
728x90
반응형
LIST