📌강의 정리
회의 시작시간과 회의의 진행시간을 기준으로 정렬하면 최대 횟수를 구하는 데 반례들이 있기 때문에 회의가 끝나는 시간을 기준으로 정렬한다.
이때 회의의 끝나는 시간이 같은 경우의 회의들은 회의의 시작시간이 빠른 순서로 정렬한다.
정렬이 끝나면 반복을 하되 매 반복마다 et변수에 끝나는 시간을 넣어 시작시간이 et보다 큰경우에만 answer++을 한다.(처음 et는 0)
📌느낀점
정말 오랜만에 알고리즘에게 제대로 당한 문제였다.
그만큼 얻어갈게 많은 아주 좋은 문제였다고 생각한다.
우선 나는 회의 시작시간과 진행시간으로는 정렬할 생각을 했는데 끝나는 시간으로는 정렬할 생각을 하지 못했다.
그것이 이 알고리즘을 제대로 풀지 못한 제일 큰 이유인데
해결방법으로는 역시 손코딩으로 종이에 알고리즘을 그려가며 우선 윤곽을 잡는 것이 맞다.
이후에 et를 이용해서 et를 업데이트하며 회의의 수를 구하는 알고리즘 또한 알고리즘의 정의에 부합하는 아주 좋은 풀이였던 것 같다.
모든 수를 반복하는게 꼭 나쁘지만은 않을 수 있다.
항상 모든 경우의 수를 염두해두고 간결하고 확실한, 그러면서도 복잡도를 챙기는 알고리즘을 생각하자.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(meeting) {
let answer = 0;
meeting.sort((a, b) => a[0] - b[0]);
meeting.sort((a, b) => a[1] - a[0] - (b[1] - b[0]));
console.log(meeting);
for (let i = 0; i < meeting.length - 1; i++) {
answer++;
if (meeting[i][1] <= meeting[i + 1][0]) i++;
}
return answer;
}
//회의를 정렬하되 순서가 처음에는
//인덱스 0을 비교하여 오름차순으로 정렬하고
//그 다음에는 인덱스 1에서 0을 뺀 수가 작은 순서로
//정렬한다. 이후 반복을 통해 최대값을 구한다.
let arr = [
[1, 4],
[2, 3],
[3, 5],
[4, 6],
[5, 7],
];
console.log(solution(arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(meeting) {
let answer = 0;
meeting.sort((a, b) => {
if (a[1] === b[1]) return a[0] - b[0];
else return a[1] - b[1];
});
let et = 0;
for (let x of meeting) {
if (x[0] >= et) {
answer++;
et = x[1];
}
}
return answer;
}
let arr = [
[1, 4],
[2, 3],
[3, 5],
[4, 6],
[5, 7],
];
console.log(solution(arr));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 7. 정렬과 그리디, 결정알고리즘' 카테고리의 다른 글
| 10.이분검색 (0) | 2022.07.08 |
|---|---|
| 9.결혼식 (0) | 2022.07.07 |
| 7.좌표 정렬 (0) | 2022.07.05 |
| 6.장난꾸러기 현수 (0) | 2022.07.04 |
| 5.Least Recently Used(카카오 캐시 문제 변형) (0) | 2022.07.03 |