📌강의 정리
그리디의 또 다른 대표적인 문제이다.
주어진 배열의 온 시간을 새로운 배열의 0인덱스, ‘s’를 1인덱스에
주어진 배열의 간 시간을 새로운 배열의 0인덱스, ‘e’를 1인덱스에 넣어 온시간 간시간들로 이루어진
원래 길이의 두배에 달하는 배열을 새로 만든다.(1인덱스가 s 또는 e인)
이후 이 배열을 오름차순으로 정렬하되 같은 시간이면 1인덱스가 e인애가 먼저오게 아스키코드를 사용하여 정렬한다.
이후 다시 반복을 하여 s이면 cnt++하고 e이면 cnt— 하여 answer와 비교하며 최대값을 측정한다.
📌느낀점
처음으로 손도 못댄 문제이다…
시간을 딱 30분으로 한정했기에 그럴 수도 있지만 시간이 더 주어졌어도 장담할 수 없다..
문제를 풀때는 이거 따로따로 다 측정하면서 계산해야 하나 라는 아주 조금은 근접한 생각을 했지만
그 생각을 컴퓨팅적으로 어떻게 간결하게 구현할지 생각이 도달하지 못했다.
이 문제를 바탕으로 앞으로 새로운 알고리즘을 짜야 할때는 이런 그리디 알고리즘을 써서 풀어보면 좋을 것 같다.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(times) {
let answer = Number.MIN_SAFE_INTEGER;
return answer;
}
let arr = [
[14, 18],
[12, 15],
[15, 20],
[20, 30],
[5, 14],
];
console.log(solution(arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<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();
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>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 7. 정렬과 그리디, 결정알고리즘' 카테고리의 다른 글
| 11.뮤직비디오(결정알고리즘) (0) | 2022.07.09 |
|---|---|
| 10.이분검색 (0) | 2022.07.08 |
| 8.회의실 배정 (0) | 2022.07.06 |
| 7.좌표 정렬 (0) | 2022.07.05 |
| 6.장난꾸러기 현수 (0) | 2022.07.04 |