알고리즘 문제풀이/백준
Baekjoon_20207_달력
Treejin
2021. 1. 17. 18:07
반응형
문제 설명
20207번: 달력
수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장
www.acmicpc.net
- 일정의 개수 N
- 시작날짜 S와 종료날짜 E가 N개 주어짐
- 일정채우기 : 시작날짜가 앞선 것부터, 같은 시작날짜라면 일정이 긴 것부터(종료날짜가 나중인 것부터)
- 전부 일정을 채운 후, 코팅지를 직사각형으로 잘라 일정을 감싼다.
=> 모든 일정을 감싸기 위해 자르는 코팅지의 최소 면적 출력
문제 풀이
우선 calender라는 클래스를 하나 만들어 시작시간과 종료시간을 저장할 수 있도록 했다.
그리고 Comparable 인터페이스를 이용해 비교하기 위한 compareTo를 만들어주었다.
시작시간을 오름차순으로 정렬하면서 만약 시작시간이 같을 경우 끝시간이 큰 것이 먼저 나오게 했다.
각 행의 최대 열값을 저장하는 배열과 각 열의 최대 행값을 저장하는 배열을 만들어 다음 그림과 같은 값이 들어가도록 구현했다.
이후 maxColumnNum이 0이 아닐때(1일)~ 0이 아닐때(10일) 안의 최대 행 값을 구하여 사각형의 너비를 구했고, 전부 더해 출력했다.
문제 풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class _20207_달력 {
static class calender implements Comparable<calender>{
int S;
int E;
calender(int S, int E){
this.S = S;
this.E = E;
}
@Override
public int compareTo(calender o) {
// TODO Auto-generated method stub
if(o.S == this.S) {
return o.E - this.E; //시작일이 같다면 끝나는 날이 큰 것부터
}
return this.S - o.S; //시작이 작은 것부터
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(in.readLine());
PriorityQueue<calender> pQueue = new PriorityQueue<>();
StringTokenizer st;
int maxColumnNum[] = new int[1001]; //각 행의 최대 열값 저장
int maxRowNum[] = new int[367]; //각 열의 최대 행값 저장
for(int i = 0; i<N;++i) {
st = new StringTokenizer(in.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
pQueue.add(new calender(S,E));
}
int maxC = 0;
while(!pQueue.isEmpty()) {
calender cal = pQueue.poll();
maxC = cal.E;
for(int r = 1; r<=1000;++r) { //일정을 위에서부터 채우면서
if(maxColumnNum[r] < cal.S) { //해당 행에 채워진 일정(최대 열값)보다 해당 일정의 시작 일자가 나중이라면
for(int i = cal.S;i<=cal.E;++i) {
maxRowNum[i] = Math.max(maxRowNum[i], r); //각 열의 최대 행 값 정정
}
maxColumnNum[r] = cal.E; //해당 행의 최대 열값을 추가한 일정의 종료일자로 변경
break;
}
}
}
int answer = 0;
for(int c = 1;c<=maxC;++c) {
if(maxRowNum[c] != 0) { //0이 아닌 부분(일정이 있는 부분)
int R = maxRowNum[c];
int startC = c; //시작 열값
while(maxRowNum[c] != 0) {
R = Math.max(R, maxRowNum[c++]); //해당 열 범위 안 최대 행 값 구하기
}
answer += R *(c - startC); //사각형 범위 값 더하기
}
}
System.out.println(answer);
}
}
반응형