자바(Java) 알고리즘 문제 풀이 - 결혼식

문제 이해

- 결혼식장에 동시에 존재하는 최대 인원수를 구하라 

 

해결 전략

- 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)과 관련된 정보가 먼저 오도록 정렬하는 것이 중요하다.