[그리디] 결혼식

문제

현수는 다음 달에 결혼을 합니다.
현수는 결혼식 피로연을 장소를 빌려 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

---

결과

O

내가 푼 방식

const solution = (arg) => {
  let array = Array.from({ length: 72 }, () => 0);

  for(let i = 0; i < arg.length; i++) {
    for(let j = arg[i][0]; j < arg[i][1]; j++) {
        array[j]++
    }        
  }
  
  array.sort((a,b) => b - a);
  return array[0];
}

 

접근과정

1. 72시간을 0의 값을 가진 72칸이라 생각하여 접근하고 배열 생성  

2. 받은 인자의 배열을 한 번 순회, 그 인자의 요소를 한 번 더 순회

3. 그 요소의 0번째 인덱스와 1번째 인덱스 사이만큼 1번의 배열에 ++ 시켜줌 

4. 1번의 배열을 내림차순으로 정렬 후 0번째 인덱스 추출 

 

모범답안

function solution(times){
    let answer=Number.MIN_SAFE_INTEGER;
    let T_line=[];
    for(let x of times){
        T_line.push([x[0], 's']);
        T_line.push([x[1], 'e']);
    }
    T_line.sort((a, b)=>{
        if(a[0]===b[0]) return a[1].charCodeAt()-b[1].charCodeAt();
        else return a[0]-b[0];
    });
    let cnt=0;
    for(let x of T_line){
        if(x[1]==='s') cnt++;
        else cnt--;
        answer=Math.max(answer, cnt);
    }
    return answer;
}

 

리뷰

1. 반환할 anwer와 타임라인을 표현할 T_line 배열을 생성 

2. 인자로 받은 times 배열을 순회하여 요소의 시작 시간으 나타내는 첫 번째 인덱스와 s로 묶고, 끝 시간을 나타내는 1번째 인덱스와 e로 묶어 T_line에 푸쉬

3. T_line을 시간대순으로 정렬하는데 시간이 같다면 아스키코드 상 e가 먼저오게 설정 다르다면 시간순으로 오름차순 

4. 변수 cnt의 값을 0으로 설정, T_line을 순회하여 두 번째 인덱스가 s를 나타내면 cnt ++ 아니마면 cnt-- 하여 answer의 값과 비교하여 둘 중 큰 값을 answer에 넣음