문제 탐색하기
입력 자료 정리
- N은 입력으로 들어오는 사람들의 수이다
- 각 입력의 첫번째는 시작시간, 두번째는 종료시간이다.
해결방법 추론
- 먼저 시간에 대한 관리는 새로운 클래스를 만들어서 한 뭉탱이로 관리를 해줄 것이다
- 그리고 배열에 입력을 받아 시작시간이 빠른 사람부터 뽑을 수 있도록 한다면
n만큼 탐색을 하면서 조건에 맞춰 확인할 수 있을 것이다 - 이어서 우선순위 큐에 종료시간을 기준으로 오름차순 정렬시켜서 넣어준다
- 가장 작은 컴퓨터의 번호를 관리할 우선순위 큐도 하나 만들어서 관리해준다
- 총 2개의 우선순위 큐와 하나의 배열로 3가지 상태를 관리한다
(사람의 이용시간, 싸지방 이용중인 컴퓨터, 번호) - 이렇게 우선순위 큐 2개와 배열 한개를 이용하여 시뮬레이션을 돌린다면, 원하는 답을 구할 수 있을 것이다.
시간복잡도 계산하기
- 시간복잡도는 n만큼 탐색하기 때문에 딱 그정도의 시간복잡도만 발생한다
- 따라서 시간복잡도는 O(n)이고 시간제한에 걸리지 않는다.
코드 설계하기
새로운 클래스 타입 생성
- Pair이라는 클래스를 하나 만들어 시작시간과 종료시간을 관리하고,
추가로 싸지방 번호도 필드로 갖는다
입력값 상태 관리하기
- Pair 클래스의 배열에 각 값을 넣어준다
정렬 설계
- 정렬은 먼저 배열의 경우 시작시간을 기준으로 오름차순 정렬한다
- 싸지방 컴퓨터의 경우 종료시간을 기준으로 오름차순 정렬을 한다
시뮬레이션 진행
- n만큼 탐색하면서 해당 사람을 싸지방을 관리하는 우선순위 큐에 넣어준다
- 그리고 컴퓨터의 최소 개수를 알기 위해 값을 증가시키고, 컴퓨터 번호를 ans로 넣어준다
- 단순히 넣어주기만 하면 안된다.
재 사람의 시작시간이 우선순위 큐의 맨앞에 있는 종료시간보다 작은 경우는 큐를 갱신해야한다 - 따라서 비어있지 않고 종료시간보다 시작시간이 빠르다면 그동안 싸지방 우선순위 큐에서 빼준
- 그 값은 컴퓨터 번호를 관리하는 우선순위 큐에 넣어주고,
이후 현재 사람을 싸지방에 넣기 전에 그 번호로 지정해준다
출력 설계
- 출력전,
computer 배열을 만들어 우선순위 큐에 있는 컴퓨터를 인덱스로 하는 위치의 값을 증가시킨다 - 이어서 ans를 출력하고, computer 배열의 각 값을 출력하면 정답이 될텐데..
시도회차 수정
1~6회차 시도 실패
- 자꾸 10%에서 틀렸습니다가 나와버렸다..
- 심지어 질문게시판의 반례들도 모두 만족시키는데도 틀리는 것을 보고,
코드 설계에 결함이 있음을 알게 되었다
코드 재 설계
- 기존에 하던 방식에서 코드를 재설계하게 되었다.
하나의 클래스에 뭉탱이로 들어있던 필드들을 뽑아내서 두개의 클래스로 만들었다 - 하나는 원래 그대로 시작시간과 종료시간을 가지는 클래스이다
- 두번째 클래스는 싸지방의 정보를 담는 클래스로 종료시간과 숫자번호를 필드로 가진다
자료구조 변경 및 추가
- 사람을 관리하는 배열도 우선순위 큐로 관리하는것이 편하다 생각하여 변경하였다
- 정렬의 경우 기존을 유지한다
- 싸지방을 관리하는 배열의 경우에도 위에서 재설계한 두번째 클래스 타입으로 하며,
종료시간을 기준으로 정렬하도록 하였다 - 번호를 관리하는 우선순위 큐는 그대로 두었는데, 한가지 초기화를 진행한다
- 미리 최대 입력으로 들어올 수 있는 번호까지 입력하여 관리하도록 하였다
- 마지막으로 출력 값을 위한 HashMap을 선언하여 관리하도록 하였다
- key는 컴퓨터 번호이고, value를 이용한 개수를 두어 출력값을 관리하도록 하였다
시뮬레이션 재설계
- 시뮬레이션도 재설계하였다. 기존 if문 이후 while문을 실행하던 것을 하나로 합쳤으며,
싸지방 우선순위 큐에서 값을 하나 뽑아서 그 중 number 필드를
번호를 관리하는 우선순위 큐에 넣어준다 - 이어서 현재 사람의 종료시간과 방번호를 싸지방 우선순위 큐에 넣어주고,
map에다가 컴퓨터 번호와 그 개수를 갱신해나간다.
출력 재설계
- 앞서 완성한 시뮬레이션으로 map만으로 모든 출력을 할 수 있게 되었다
- 컴퓨터의 최소 개수는 map의 크기이고, 각 값을 for-each로 하나씩 출력하면 정답이 된다
문제 리마인드
- 하나의 클래스에 다 몰아 넣을 생각보다는 분리해서 관리하는 것도 방법이다
- 상태를 관리할 값에 대해 자료구조를 고민해보고,
뭔가 논리에 맞지 않다면 다른 자료구조 사용을 고민해보자
7회차 시도 성공
정답 코드
(1~6회차 시도 실패)
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
class Pair{
int start = 0;
int end = 0;
int computer;
public Pair(int start, int end, int computer) {
this.start = start;
this.end = end;
this.computer = computer;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
Pair[] pairs = new Pair[n];
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
pairs[i] = new Pair(start, end, Integer.MAX_VALUE);
}
Arrays.sort(pairs, (o1, o2) -> {
return o1.start - o2.start;
});
PriorityQueue<Pair> pq = new PriorityQueue<>((o1, o2)->{
return o1.end - o2.end;
});
int ans = 0;
PriorityQueue<Integer> smallComputer = new PriorityQueue<>();
for (int i = 0; i < n; i++) {
if(!pq.isEmpty() && pq.peek().end <= pairs[i].start){
while(!pq.isEmpty() && pq.peek().end <= pairs[i].start){
smallComputer.add(pq.poll().computer);
}
pairs[i].computer = smallComputer.poll();
pq.add(pairs[i]);
continue;
}
pairs[i].computer = ans;
ans++;
pq.add(pairs[i]);
}
int[] computers = new int[n];
for (int i = 0; i < n; i++) {
computers[pairs[i].computer]++;
}
bw.write(ans+"\n");
for (int i = 0; i < ans; i++) {
bw.write(computers[i] +" ");
}
br.close();
bw.close();
}
}
1~6회 시도까지 비슷해서 6회차 시도 코드만 가져옴
(7회차 시도 성공!)
import java.io.*;
import java.util.*;
/**
* 풀이 과정:
* - 고민과 풀이:
*
* - 문제 해결:
*
* 시간복잡도: O()
* 공간복잡도: O()
*
*/
class Person{
int start;
int end;
public Person(int start, int end) {
this.start = start;
this.end = end;
}
}
class Room{
int end;
int number;
public Room(int end, int number) {
this.end = end;
this.number = number;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
PriorityQueue<Person> pairs = new PriorityQueue<>((o1, o2)->{
if(o1.start == o2.start){
return o1.end - o2.end;
}
return o1.start - o2.start;
});
for (int i = 0; i < n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
pairs.add(new Person(start, end));
}
PriorityQueue<Integer> number = new PriorityQueue<>();
PriorityQueue<Room> room = new PriorityQueue<>((o1,o2) -> {
if(o1.end == o2.end){
return o1.number - o2.number;
}
return o1.end - o2.end;
});
for (int i = 1; i < 100001; i++) {
number.add(i);
}
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
while(!room.isEmpty() && room.peek().end < pairs.peek().start){
number.add(room.poll().number);
}
Person person = pairs.poll();
int num = number.poll();
map.put(num, map.getOrDefault(num, 0) + 1);
room.add(new Room(person.end, num));
}
bw.write(map.size()+"\n");
for (Integer value : map.values()) {
bw.write(value +" ");
}
br.close();
bw.close();
}
}문제 링크
Software Developer