[기초 알고리즘] 봉우리 - 자바스크립트

문제

지도 정보가 N*N 격자판에 주어진다. 각 격자에는 그 지역의 높이가 쓰여 있다.

각 격자판의 숫자는, 자신의 상하좌우 숫자보다 큰 숫자를 가졌을 때 봉우리라고 불린다.

N*N 격자판에서 봉우리가 몇 개 있는지 알아내보자.

격자의 가장자리는 0으로 초기화 되었다고 가정한다.

그러므로 N=5이고 격자판의 숫자가 아래와 같다면, 봉우리 개수는 10이 출력되어야 한다.

 

그림1) 5*5 격자판과 봉우리들

 

나의 풀이

 

1. 각 격자를 조회하기 위해 2중 for문을 돌려야 한다.
2. 5*5의 격자에서 가장자리에 있는 높이들을 평가할 때, 배열의 범위를 벗어나는 참조를 주의한다.

function solution(arr){
	const n = arr.length;
	let peakCount = 0;
    
    for(let i = 0; i < n; i++){
    	for(let j =0; j< n; j++){
        	if(arr[i-1][j] && arr[i-1][j] >= arr[i][j]) break;
            if(arr[i+1][j] && arr[i+1][j] >= arr[i][j]) break;
            if(arr[i][j-1] && arr[i][j-1] >= arr[i][j]) break;
            if(arr[i][j+1] && arr[i][j+1] >= arr[i][j]) break;
            peakCount++;
		}
	}
    return peakCount;
}


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));

 

 

다음과 같이 작성을 했다.

• 이중 for문 안에서, 상하좌우에 따라 현재 격자 값 보다 상하좌우값이 하나라도 크다면  봉우리가 아니므로 j for문을 break로 탈출한다.
• if문에서, 2개의 조건을 모두 만족해야 하는데 첫번째 조건에서 arr[i-1][j] 가 arr[-1][0]이라면, undefined가 발생하여 if문 안에서 undefined를 false로 인식해서 if문을 무난히 넘길 수 있다고 생각했다.
• 마지막으로 만약 If문을 모두 통과했으면, arr[i][j]보다 더 높은 격자가 상하좌우에 없으므로, 봉우리 개수를 올려준다.

 

 

※ 에러 발생

그림2) 발생한 로그

다음의 에러를 내뿜는다.

undefined의, 0 이라는 속성을 읽을 수가 없다고 한다.

 

그림3) 코드를 작성하기 앞서 테스트용으로 실행해본 결과

•  

분명히 콘솔에서 배열을 벗어나면 undefined가 리턴되는 것을 확인했는데, 예상하지 못한 에러였다.

열심히 구글링해서 알아 보니,

 

자바스크립트에서는 배열의 범위를 벗어나는 곳을 참조해도 에러가 발생하지 않는다.

대신 undefined를 반환하므로, a[3]의 결과가 undefined가 된다.

 

그런데, a가 참조하는 배열이 이중 배열이라면, 아래와 같다.

const a = [[1,2], [3,4]];

a[2][2] // 연산의 순서를 고려하면 (a[2])[2] 로 바꿀 수 있다.
		// 그러므로 첫번째 인덱스 연산자로부터 배열을 반환받고, 다시 참조하는 구조가 되는데
        // a[2]는 배열의 범위를 넘어섰으므로, undefined가 된다.
        // a[2][2] -> (undefined)[2] 가 된다.
        // 그러므로 undefined에서 2번째 인덱스를 찾는 것은 불가능하다.
        // 그 결과로 `Cant read property '2' of undefined` 에러가 발생한다.

 

이중 for문 안에 추가의 for문을 넣기 싫어서, 나름 머리를 굴린다는게 결국 아무것도 실행되지 않는 결과를 보여줬다.

 

 

 

새로운 풀이

 

 

1. 배열의 undefined를 이용하지 않고, 격자의 상하좌우 인덱스가 배열 내부 인덱스에 존재할 때만을 고려한다.
2. if문을 남발하지 않고, 상하좌우 4번을 동작하는 for문을 내부에 추가한다.
   1. 이 for문을 위해서 상하좌우의 움직임이 담긴 배열을 추가한다.

function solution(arr){
	const n = arr.length;
    let peakCount = 0;
    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 < dx.length; 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) peakCount++;
           }
       }
   }
   return peakCount;
}

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));

 

• dx, dy는 각각 12시, 3시, 6시, 9시로 움직이는 x, y 이동값이 담긴 배열이다.
• 2중 for문을 돌면서 N*N 격자판의 모든 격자를 조회한다.
• (i, j) 위치를 기준으로 상하좌우 값을 조회하기 위해 for문 안에 if문을 넣었다.
  • 탈출을 감지하기 위해서 flag변수를 먼저 1(true)로 선언한다.
  • if문에서는 상하좌우 인덱스가 격자판의 인덱스를 벗어나지 않으며, 상하좌우 값이 기준값보다 크다면 flag변수를 0으로 바꾸고 탈출한다.
  • 만약 flag변수가 1이라면(변하지 않았다면), 해당 격자는 봉우리이므로 갯수를 세준다.

 

그 결과, 정답인 10이 반환된다.

 

 

느낀점

 

항상 알고리즘 문제를 풀 때, 글이 길어지거나 조금 복잡해보이거나 하면 시야가 더 좁아지는 경향이 있다.

변수를 적게 선언하고, 최대한 깔끔해보이게 작성하고 싶은 마음에 사로잡혀서 어떤 기초적인 원리에 대한 고려 없이 생각나는 대로 코드를 짜기도 한다.

 

그로 인해서, 작게 분해하면 쉽게 해결할 수 있는 문제를, 어렵게 생각해서 어려운 방향으로 가는 일이 잦다.

이 문제에서 닥친 상황과 같이, 근본적인 코드 작동 원리를 이해하지 못해서 에러를 발생시키는 일도 있고,

너무 어렵게 생각해서 코드가 엄청나게 길어져버리면 좌절하고 정답을 찾는데, 너무 쉽게 해결되어 버리는 답을 보고 기운이 빠지기도 한다.

 

 

결국 이런 문제는 처음부터 코드를 완벽하게 짜고 싶다는 생각 때문에 발생한다.

알고리즘 문제는 아무래도 시간에 쫓기다보니 더 마음을 가지게 되고, 결국 문제를 풀지도 못하는 상황이 되는 듯 하다.

 

복잡한 문제는 작은 부분으로 나눠서 생각하고, 처음부터 완벽한 코드가 아닌 우선 작동하는 코드를 짜고 내가 짠 코드를 보면서 코드 슬림화에 대해 고려 하는 방식으로 다시 학습 해야겠다.