[JavaScript/section 7] 09 - 결혼식

📌 09 - 결혼식(그리디 알고리즘)

피로연 장소에 동시에 존재하는 최대 인원수를 구하는 문제이다. 한 친구가 오는 시간이 13, 가는 시간이 15라면 이 친구는 13시 정각에 피로연 장에 존재하는 것이고 15시 정각에는 존재하지 않는다고 가정한다.

나의 풀이 방법

• 오는 시간(s)과 가는 시간(e)을 나누어 따로 배열을 만든 다음 오름차순 정렬을 한다.
• 투 포인터 알고리즘을 사용하여 p1이 p2보다 크거나 같으면 새로운 배열에 가는 시간(e)를 추가하고 p2++을 한다.
• p1이 p2보다 작다면 오는 시간(s)를 추가하고 p1++을 한다.
• for 문을 돌면서 's'가 나오면 cnt++을 해주고 'e'가 나오면 cnt--를 해준다.
• 피로연 장소에 들어오거나 나가는 사람이 발생할 때마다 피로연 장소에 존재하는 인원수와 answer를 비교하여 더 큰 값을 answer에 저장한다. 

👍 강사님 풀이 방법

문자열을 순서대로 비교하여 오름차순으로 정렬하기 위해 단어 정렬 문제에서 '>', '<' 연산자를 사용했다. 강사님의 풀이 방법에서는 charCodeAt() 함수를 이용해 ASCII 코드로 바꿔준 다음 순서대로 비교한다.

• for 문을 돌면서 한 친구의 오는 시간(s)과 가는 시간(e)을 나누어 배열 형식[시간, 's' or 'e']으로 배열에 추가한다.
• 시간을 기준으로 오름차순 정렬을 하는데 오는 시간(s)과 가는 시간(e)이 동일하면 문자열을 비교하여 정렬한다.
• for 문을 돌면서 's'가 나오면 cnt++을 해주고 'e'가 나오면 cnt--를 해준다.
• 피로연 장소에 들어오거나 나가는 사람이 발생할 때마다 피로연 장소에 존재하는 인원수와 answer를 비교하여 더 큰 값을 answer에 저장한다.

 

📝 풀이

// 나의 풀이 방법
function solution(times) {
  let answer = Number.MIN_SAFE_INTEGER;
  let s = times.map((time) => time[0]).sort((a, b) => a - b);
  let e = times.map((time) => time[1]).sort((a, b) => a - b);
  let se = [];
  let p1 = (p2 = cnt = 0);

  while (p1 < s.length && p2 < e.length) {
    if (s[p1] === e[p2] || s[p1] > e[p2]) {
      se.push('e');
      p2++;
    } else {
      se.push('s');
      p1++;
    }
  }

  if (p1 === s.length) {
    while (p2 < e.length) {
      se.push('e');
      p2++;
    }
  } else {
    while (p1 < e.length) {
      se.push('s');
      p1++;
    }
  }

  for (let x of se) {
    if (x === 's') cnt++;
    else cnt--;
    answer = Math.max(answer, cnt);
  }

  return answer;
}

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

// 강사님 풀이 방법
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;
}

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