2022/03/21) 9. 결혼식 [정렬과 그리디, 결정알고리즘]
1. 문제
<결혼식>
: 결혼식 피로연을 3일간 쉬지 않고 하려고 하는데, 참석하는 친구들(N명)의 참석하는 시간정보를 미리 요구했다. 이 정보를 바탕으로 피로연 장소에 동시에 존재하는 최대 인원수를 구하여 그 인원을 수용할 수 있는 장소를 빌리려고 한다. 피로연장에 동시에 존재하는 최대 인원을 출력하라.
2. 해결 방법
- 타임라인으로 그림을 그려본 후, 도착하는 시간을 's'로 떠나는 시간을 'e'로 해서 새 배열(T_line)을 만들어 보자.
- 그 후 새배열을 정렬하는데, 같은 시간대일 경우엔 e->s 순으로 정렬한다.(유니코드 이용)
sort함수는 반환값이 0보다 작으면 a를 우선하여 정렬한다는 거 명심!- 's'를 만나면 cnt++, 'e'를 만나면 cnt--를 한다. 그 후 Math.max로 answer과 cnt의 값을 비교해서 큰 값을 answer에 넣는다.
3. 정답
<script> 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(); //시간이 같을 땐 e가 먼저 오도록 해야함 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)); </script>
4. 후기
그리디가 무조건 끝의 시간으로 정렬하는 게 아니구나. 그냥 문제에 따라 오름차순 혹은 내림차순으로 정렬하는 게 그리디정렬인 거 같다. 조금 헷갈리는데 그림그려서 해보도록 하자!
Author And Source
이 문제에 관하여(2022/03/21) 9. 결혼식 [정렬과 그리디, 결정알고리즘]), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@7lo9ve3/20220322-9.-결혼식-정렬과-그리디-결정알고리즘저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)