봉우리 갯수 구하기

:raising_hand: 알고리즘 공부 간 기록이 필요한 문제들에 대한 정리를 기록하는 포스트 입니다.

1. 문제 요건

  1. N X N 길이의 격자판에서 상하좌우 값보다 큰 경우 봉우리로 인정 및 Count
  2. 주어진 N X N 배열 가장자리는 0 으로 가정하여 전체 봉우리의 갯수 를 구하라.

2. 코드

먼저 문제를 보자마자 기억나는 아이디어는 합을 모두 구해서 배열에 담고 비교하자 였다.

그래서 보자마자 아래와 같이 빠르게 작성을 해보았다.

// 네방향 탐색 Key Point
// 1. 상, 하, 좌, 우 네방향을 검사하기 위한 사전 dx,dy 값 정의
// 2. 반복문을 통해 검증 간 가장자리 필요없는 부분에 대한 배제 조건 정의

function solution(arr) {
    let answer = 0
    let n = arr.length
    // 상,하,좌,우
    let dx = [-1,1,0,0]
    let dy = [0,0,-1,1]

    for(let i = 0; i < arr.length; i++) {
        for(let j = 0; j < arr.length; j++) {
            // 기본 값으로 1을 넣어놓고 상,하,좌,우 탐색 중 큰게 있으면 취소
            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 < 5) && (ny >= 0 && ny < 5) && arr[nx][ny] > arr[i][j]) {
                    flag = 0
                    break
                }
            }
            
            if(flag === 1) {
                answer++
            }
        }
    }
    return answer
}

3. 결과정리

이 문제의 Key 포인트는 네방향 탐색이다.

내가 먼저 문제를 풀면서 놓친 부분은 문제에서 검증의 대상(상,하,좌,우) 에 대한 방향값을 사전에 배열로 정의하는 부분이다.

가장 처음 문제를 접근할때 이부분을 놓쳤기 때문에 반복문 내에서 조건으로 이를 해결하려고 하였다.

즉, 가장 바깥쪽에 있는 부분에 대해서는 상,하,좌,우 값이 없으니 이부분에 대하여 조건처리로 해결해도 풀리기는..? 할 것이다.

그러나 직접 풀어본 나로서는 너무 복잡해지고 절대 옳지 않은 코드가 완성될 것이다.

위에서 푼 아이디어 처럼 상,하,좌,우 값의 행(dx), 열(dy) 값을 먼저 정해둔 후 반복문을 통해 검증 대상 arr[i][j] 값을 특정 한 뒤에 반복문을 통해 상,하,좌,우 값을 검증해 나가는 방법이 훨씬 좋은 아이디어 이다.

N X N 배열에서 상,하,좌,우 혹은 주변 값을 검증할 떄에는 검증 조건에 해당하는 위치를 먼저 선정하자

You may also enjoy