인프런 js 알고리즘 강의를 듣고 공부한 내용을 정리한 게시글입니다.
1.등수 구하기 알고리즘
function solution(arr) {
let n = arr.length;
let answer = Array.from({ length: n }, () => 1);
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length; j++) {
console.log(arr[i], arr[j]);
if (arr[i] < arr[j]) answer[i]++;
}
}
return answer;
}
console.log(solution([87, 89, 92, 100, 76]));
풀이:answer 을 등수가 담긴 배열로 return 해야 하기 때문에 Array.from 을 이용해 길이가 n만큼 그리고 콜백함수를 이용해 1로 초기화 시켜줬습니다.
그리고 이중 for문을 돌면서 arr[i] 가 arr[j] 보다 작으면 등수가 올라가도록 설정해놓고 answer을 return 하였습니다.
2.격자판 알고리즘
function solution(arr) {
let answer = Number.MIN_SAFE_INTEGER;
let n = arr.length;
let sum1 = (sum2 = 0);
for (let i = 0; i < n; i++) {
sum1 = sum2 = 0;
for (let j = 0; j < n; j++) {
sum1 += arr[i][j];
sum2 += arr[j][i];
}
answer = Math.max(answer, sum1, sum2);
}
sum1 = sum2 = 0;
for (let i = 0; i < n; i++) {
sum1 += arr[i][i];
sum2 += arr[i][n - i - 1];
}
answer = Math.max(answer, sum1, sum2);
return answer;
}
let arr = [
[10, 13, 10, 12, 15],
[12, 39, 30, 23, 11],
[11, 25, 50, 53, 15],
[19, 27, 29, 37, 27],
[19, 13, 30, 13, 19],
];
console.log(solution(arr));
풀이: 이제부터 좀 난이도가 올라가서 푸는데 시간이 많이 걸렸습니다.
일단 풀이를 설명 드리자면
이렇게 격자판이 있는데 행과 열 그리고 대각선 더한값중에 가장 큰 값을 구하는 알고리즘입니다.
먼저 행 그리고 열을 다 더한값을 알아야 합니다.
그러기 위해서 sum1은 행을 더한 값, sum2는 열을 더한값으로 변수를 선언해줬습니다. 둘다 0으로 값을 할당 해줬습니다.
sum1=sum2=0;
이중 포문을 이용해서 arr[행][열] 이라고 생각 했을때 ,
행을 더한 값이고 arr[i][j] 는 행을 더한 값이고, arr[j][i] 는 열을 더한 값이라고 생각하면 된다. 이중 포문이 다 돌았을때 answer =Math.max(answer,sum1,sum2) 에서 최댓값을 구해줬습니다.
그리고 다시 행을 더한 값, 열을 더한 값을 0으로 초기화 시켜주었습니다.
초기화를 시킨 이유는 이제 대각선 더한 값을 구하기 위함입니다.
sum1은 아래 대각선 sum2 는 위로 올라가는 대각선의 합을 뜻합니다.
아래로 내려가는 대각선은 각 행과 열이 같습니다
[0,0],[1,1][2,2][3,3][4,4] 그렇기 때문에 식은 arr[i][i] 입니다.
위로 올라가는 대각선은 [0,4],[1,3],[2,2],[3,1],[4,0] j는 1씩 감소 합니다. 인덱스는 실제 격자판 보다 1이 더 많기 때문에 n-i 에서 -1을 더 빼줍니다. (인덱스는 0부터 세고 격자판은 1부터 세는 차이) (n-i-1)
for문이 끝나면 다시 최댓값을 구해줍니다 . 그리고 최종적으로 answer을 return 시켜줘서 행과 열 그리고 대각선 값까지 해서 제일 큰 합을 최종적으로 출력 합니다.
3.봉우리 구하는 알고리즘
(오랜시간 들여 풀어봤지만 오답.. 오답 노트 해야겠다.)
그래도 문제의 방향성은 맞는거 같다.
function solution(arr) {
let answer = 0;
let n = arr.length;
for (let i = 1; i < n; i++) {
for (let j = 1; j < n; j++) {
if (
arr[i][j] > arr[i - 1][j] &&
arr[i][j] > arr[i + 1][j] &&
arr[i][j] > arr[i][j + 1] &&
arr[i][j] > arr[i][j - 1]
) {
answer++;
}
}
}
return answer;
}
let arr = [
[5, 3, 7, 2, 3],
[3, 7, 1, 6, 1],
[7, 2, 5, 3, 4],
[4, 3, 6, 4, 1],
[8, 7, 3, 5, 2],
];
console.log(solution(arr));
정답 코드
function solution(arr) {
let answer = 0;
let n = arr.length;
let dx = [-1, 0, 1, 0]; //행
let dy = [0, 1, 0, -1]; //열
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
let flag = 1;
for (let k = 0; k < 4; k++) {
let nx = i + dx[k];
let ny = j + dy[k];
if (
nx >= 0 &&
nx < n &&
ny >= 0 &&
ny < n &&
arr[nx][ny] >= arr[i][j]
) {
flag = 0;
break;
}
}
if (flag) answer++;
}
}
return answer;
}
let arr = [
[5, 3, 7, 2, 3],
[3, 7, 1, 6, 1],
[7, 2, 5, 3, 4],
[4, 3, 6, 4, 1],
[8, 7, 3, 5, 2],
];
console.log(solution(arr));
풀이:
일단 봉우리를 찾기 위해서 우리가 해야할일은 해당 행과 열의 있는 숫자와 상하좌우를 살펴야 한다. 상하좌우를 살피기 위해서는
arr[i][j] 라고 했을때
dx= [-1,0,1,0]
dy=[0,-1,0,1] 만든다.
만들고 난 후 이중 for문을 돌려서 행과 열을 탐색 시킨다.
포문을 하나 더 돌려서 dx와 dy를 탐색할 수 있게 한다.
가려는 방향은 nx=i+dx[k] 행 방향 그리고 ny=j+dy[k] 열방향을 뜻합니다.
이제 arr[nx][ny] (상하좌우를 뜻합니다) 가 arr[i][j] (해당 행열의 숫자를 뜻합니다.)보다 작거나 같으면 봉우리가 아니기 때문에 여기서 바로 break 를 시켜줘서 봉우리가 아니면 상하좌우를 살필 필요가 없기 때문에 멈춰 줍니다. flag는 봉우리인지 아닌지를 카운트 시켜주는 매개체 입니다.
봉우리가 아니라면 flag를 0으로 바꿔줍니다. flag가 1이면 true 이고 flag가 0이면 boolean 값으로 false 입니다. flag가 만약 true 라면 봉우리라는 의미이기 때문에 최종적으로 answer을 카운팅 해줌으로써 봉우리가 몇개인지 알수있습니다.
여기서 중요한 점은 nx와 ny 의 범위를 잘 정해야 합니다. 아니면 인덱스 범위를 초과하게 되어 out of index 에러가 발생할 수 있습니다.
문제에서 가장자리는 모두 0이라고 되어있기 때문에 nx 는 무조건 0보다 크거나 같을 수 있습니다. nx >=0 && 그리고 nx는 n인 arr의 length 를 초과할 수 없기 때문에 nx < n 보다 작아야합니다. 이렇게 조건을 걸어줘서 인덱스가 올바른 범위를 탐색할 수 있게 해야합니다.!
