섹션 9. Greedy Algorithm 3. 결혼식

문제

• 현수는 다음 달에 결혼을 합니다.
• 현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.
• 피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.
• 각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.
• 현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다. 여러분이 현수를 도와주세요.
• 만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다.

입력

• 첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.
• 두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.
• 시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다.

출력

• 첫째 줄에 피로연장에 동시에 존재하는 최대 인원을 출력하세요.

입출력 예제

---

풀이방식

이번 문제는 그리디 알고리즘에 대한 문제이다.

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

---

설계과정

1. People 객체에 시간과 문자를 담아서 오는 시간과 가는 시간을 구분한다.

2. 시간상 정렬을 하고, 시간이 동일하면 알파벳을 기준으로 오름차순 정렬한다.

3. People 객체와 arr 배열을 하나씩 비교해서 오는 시간이면 cnt++, 가는 시간이면 cnt--를 수행한다.

4. result와 cnt를 비교하여 더 큰 값을 출력한다.

---

풀이과정

1. 각 변수들을 선언한다.

• 시간과 문자를 갖고 있는 클래스 People를 가진 ArrayList 배열  arr[ ] 을 선언한다.
• 시간을 의미하는 변수 time 을 선언한다.
• 각 시간이 오는 시간인지 가는 시간인지에 대한 값을 갖고있는 변수 state 을 선언한다.
• 그 시각에 존재하는 인원수 cnt 을 선언한다.

2. 시간과 문자를 갖고 있는 People 객체를 배열에 넣어서 오름차순으로 정렬한다.

 

3. 만약 시간이 동일하다면 문자를 기준으로 오름차순 정렬한다.

• 오름차순이어야 'e' 가 앞으로 나와서 해당 시간에 없는 이를 먼저 작업할 수 있다.

4. for문을 통해 People 객체와 arr 배열을 각각 비교해서 오는 시간이면 cnt를 더하고, 가는 시간이면 cnt를 뺀다.

• stats == 's' 이면 오는 시간이므로 인원이 추가되는 것이기에 cnt를 추가한다.

5. for문을 통해 Time 객체와 arr 배열을 각각 비교해서 시작 시간이 끝나는 시간보다 크거나 같으면 cnt를 누적한다.

 

6. result와 cnt를 비교하여 더 큰 값을 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.