PS
자바(Java) 알고리즘 문제 풀이 - 결혼식
Bryan Lee
2022. 4. 24. 20:21
문제 이해
- 결혼식장에 동시에 존재하는 최대 인원수를 구하라
해결 전략
- ArrayList에 시간과 관련된 정보를 저장합니다
-> 해당 ArrayList를 정렬합니다.
- ArrayList를 순회하면서 s와 관련된 정보일 때는 인원을 추가하고,
e와 관련된 정보일 때는 인원을 감소시킵니다.
구현
import java.util.*;
class Time implements Comparable<Time>{
public int time;
public char state;
Time(int time, char state) {
this.time = time;
this.state = state;
}
@Override
public int compareTo(Time ob){
if(this.time==ob.time) return this.state-ob.state;
else return this.time-ob.time;
}
}
class Main {
public int solution(ArrayList<Time> arr){
int answer=Integer.MIN_VALUE;
Collections.sort(arr);
int cnt=0;
for(Time ob : arr){
if(ob.state=='s') cnt++;
else cnt--;
answer=Math.max(answer, cnt);
}
return answer;
}
public static void main(String[] args){
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n=kb.nextInt();
ArrayList<Time> arr = new ArrayList<>();
for(int i=0; i<n; i++){
int sT=kb.nextInt();
int eT=kb.nextInt();
arr.add(new Time(sT, 's'));
arr.add(new Time(eT, 'e'));
}
System.out.println(T.solution(arr));
}
}
피드백
- ArrayList에 오는 시간(s)와 가는 시간(e)와 관련된 정보를 구분해서 저장하는 것이 중요하다.
- 시간순으로 정렬하고, 시간이 같으면 가는 시간(e)과 관련된 정보가 먼저 오도록 정렬하는 것이 중요하다.