📌강의 정리
오름차순 정렬 이후에 이분탐색을 이용하여 타겟을 찾는다.
이분탐색은 while, lt, rt, mid를 이용한다.
lt가 rt보다 커지면 반복을 종료하고, 반복내에서는 arr[mid]가 타겟과 같으면 answer = mid+1하고 break한다.
아닌경우 mid가 타겟보다 작으면 rt는 mid - 1, mid가 타겟보다 크면 lt는 mid + 1을 해서 반복한다.
📌느낀점
알고리즘은 진짜 넓게 배울필요도 있는 것 같다.
이분탐색을 알고는 있었지만 처음 구현해보는데
내가 푼 풀이도 가능은 하지만 강사님의 풀이가 훨씬 직관적이고 깔끔하다.
lt와 rt를 생각하지못했다..
항상 사고의 확장을 조금 더 신경써보자.
//나의 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(target, arr) {
let answer;
let len = Math.floor(arr.length / 2);
arr.sort((a, b) => a - b);
console.log(arr);
for (let i = 0; i < arr.length / 2; i++) {
if (target < arr[len]) len = Math.floor(len / 2);
else if (target > arr[len]) len += Math.floor(len / 2);
else {
if (target === arr[len]) answer = len + 1;
else answer = arr.length;
}
}
return answer;
}
//오름차순으로 먼저 정렬한다.
//이분검색으로 몇번째에 있는지 구한다.
let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(99, arr));
</script>
</body>
</html>
//강사님 코드
<html>
<head>
<meta charset="UTF-8" />
<title>출력결과</title>
</head>
<body>
<script>
function solution(target, arr) {
let answer;
arr.sort((a, b) => a - b);
let lt = 0,
rt = arr.length - 1;
while (lt <= rt) {
let mid = parseInt((lt + rt) / 2);
if (arr[mid] === target) {
answer = mid + 1;
break;
} else if (arr[mid] > target) rt = mid - 1;
else lt = mid + 1;
}
return answer;
}
let arr = [23, 87, 65, 12, 57, 32, 99, 81];
console.log(solution(32, arr));
</script>
</body>
</html>
'JS 알고리즘 문제풀이 > 섹션 7. 정렬과 그리디, 결정알고리즘' 카테고리의 다른 글
| 12.마구간 정하기(결정알고리즘) (0) | 2022.07.11 |
|---|---|
| 11.뮤직비디오(결정알고리즘) (0) | 2022.07.09 |
| 9.결혼식 (0) | 2022.07.07 |
| 8.회의실 배정 (0) | 2022.07.06 |
| 7.좌표 정렬 (0) | 2022.07.05 |