결혼식 - 그리디 알고리즘

문제

현수는 다음 달에 결혼을 합니다.

현수는 결혼식 피로연을 장소를 빌려 3일간 쉬지 않고 하려고 합니다.

피로연에 참석하는 친구들 N명의 참석하는 시간정보를 현수는 친구들에게 미리 요구했습니다.

각 친구들은 자신이 몇 시에 도착해서 몇 시에 떠날 것인지 현수에게 알려주었습니다.현수는 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 합니다.

여러분이 현수를 도와주세요.

만약 한 친구가 오는 시간 13, 가는시간 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정합니다

 

🍹 입력설명

첫째 줄에 피로연에 참석할 인원수 N(5<=N<=100,000)이 주어집니다.

두 번째 줄부터 N줄에 걸쳐 각 인원의 오는 시간과 가는 시간이 주어집니다.

시간은 첫날 0시를 0으로 해서 마지막날 밤 12시를 72로 하는 타임라인으로 오는 시간과 가는 시간이 음이 아닌 정수로 표현됩니다

 

🍹 출력 

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

 

🍹 입력예제 1

5
14 18

12 15

15 20

20 30

5 14

 

🍹 출력 예제 1

2

 

풀이

입력된 배열값을 시작시간 기준으로 정렬해보면 아래와 같다.

 

이것을 아래 그림으로 보면 이렇다.

정렬된 타임라인

 

시작시간일때는 카운트를 1 올려준다

 

 

끝나는 시간을 만났을때는 카운트를 1 줄여준다. 타임라인이 끝날 때까지 이런 방식으로 계산해준다.

 

위와 같은 카운트를 해주기 위해서 입력된 배열값을 쪼개서 새로운 배열에 입력해준다

배열을 숫자를 기준으로 오름차순해준다. 숫자가 같으면 끝나는 시간인 'e'가 먼저 오도록 한다.

이제 위의 배열을 반복문을 돌면서 s를 만나면 count++하고, e를 만나면 count--한다.

count를 하면서 동시에 answer값을 넣어줘서 값을 최신화시킨다.

반복문을 마치면 answer값을 리턴해준다.

 

코드

function solution(times){
  let answer = 0;
  let count = 0;
  let timeline = [];
  times.map(item => {  // 1
    timeline.push([item[0], 's'])
    timeline.push([item[1], 'e'])
  })
  timeline.sort((a, b) => {  // 2
    if (a[0] === b[0]) return a[1].charCodeAt() - b[1].charCodeAt()
    return a[0] - b[0]
  })
  for (let x of timeline) {  // 3 
    if (x[1] === 's')count++;
    else count--;
    answer = Math.max(answer, count)
  }  
  return answer;
}

let arr=[[14, 18], [12, 15], [15, 20], [20, 30], [5, 14]];
console.log(solution(arr)); // 2

1. 먼저 입력된 times를 각 항목마다 시작요소에는 's'를 끝요소에는 's'를 넣어서 timeline배열에 넣는다.

2. timeline배열의 시간을 기준으로 오름차순 정렬. 시간이 똑같다면 끝나는 시간이 먼저 오도록 한다.

3. 's' 가 나오면 count++, 'e'가 나오면 count--를 해주고 count해줄때마다 answer값을 최신화 시킨다.

출처

자바스크립트 알고리즘 문제풀이(코딩테스트 대비) - 인프런 | 강의