[인프런] 02_10 봉우리

📖  문제

---

• 첫 줄에 자연수 N이 주어진다
  • 지도 정보가 N * N 격자판이 주어진다. (격자에는 그 지역의 높이가 쓰여있다.)
  • 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역이다. 
  • 격자판의 가장자리는 0으로 초기화돼있다고 가정한다.
• 봉우리 지역이 몇 개 있는지 출력하기.
• 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개이다.

출처) 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비

 

 

⚠️  주의사항

---

• 상하좌우로 비교해야 하는데 (0,0)의 경우에는 왼쪽 위가 둘 다 null 값이라서 비교하려고 하면 오류가 난다.
  • 가장자리가 0으로 초기화돼있다는 점을 이용해서 풀면 된다.
• 상하좌우 비교를 어떻게 하면 좋을지 생각해보기

 

✍️  이해

---

두 가지의 이해 내용이 있습니다. 아래는 제가 맨 처음 문제를 보고 이해하고 이렇게 풀면 되겠다 싶어서 적어 둔 것이 있습니다.

* 1. N * N 격자판 주어짐 가장자리는 0이라고 했으므로 [N+2][N+2]으로 해야된다.
* 2  가장자리에서 시작 할 필요가 없으므로 for문 할 때 i, j = 1 시작
* 3. temp[i][j] > temp[i+1/-1][j+1/-1] 경우 cnt ++

---

* 1. if 문 4개짜리 안쓰는 이유 -> 4방향이 아닌 8방향인 경우 if문 8개 16방향이면 16개 이렇게 필요해져서 코드가 복잡해짐
* 2. 위 오른쪽 아래 왼쪽 순으로 비교하게 됨
* 3. boolean 으로 체크 해서 true 일 때만 answer++
* 4. N + 2 해서 가상의 행과 열을 만드는 방법은 좋지 않은 방법임 필요 없는 행과 열이 생기기 때문

위 내용은 첫 수업을 듣고 코드를 정비하면서 적은 내용이다. 

 

이해 내용이 2개 있는 것처럼 풀이 코드도 2개가 있습니다.

 

✏️  풀이

---

1. 따로 찾아보지 않고 직접 풀어본 코드입니다. 그만큼 날것의 코드이며 잘못된 점이 많습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * 1. N * N 격자판 주어짐 가장자리는 0이라고 했으므로 [N+2][N+2]으로 해야된다.
 * 2  가장자리에서 시작 할 필요가 없으므로 for문 할 때 i, j = 1 시작
 * 3. temp[i][j] > temp[i+1/-1][j+1/-1] 경우 cnt ++
 */
public class Java_02_10_1 {

    public int solution(int N, int[][] temp) {

        int cnt = 0;

        for (int i = 1; i <= N ; i++) {
            for (int j = 1; j <= N ; j++) {

                if (temp[i][j] > temp[i + 1][j] && // 아래
                        temp[i][j] > temp[i - 1][j] && // 위
                        temp[i][j] > temp[i][j + 1] && // 오른쪽
                        temp[i][j] > temp[i][j - 1]) { // 왼쪽
                    cnt++;
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) throws IOException {

        Java_02_10_1 T = new Java_02_10_1();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[][] temp = new int[N+2][N+2];

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int j = 1; j <= N; j++) {
                int num = Integer.parseInt(st.nextToken());
                temp[i][j] = num;
            }
        }

        System.out.println(T.solution(N, temp));
    }
}

하지만 이 코드는 빈 배열을 추가적으로 만들어버린다는 안 좋은 코드입니다. 이것을 보완한 코드가 있습니다.

---

 

2. 보완 코드

import java.util.*;

/**
 * 1. if 문 4개짜리 안쓰는 이유 -> 4방향이 아닌 8방향인 경우 if문 8개 16방향이면 16개 이렇게 필요해져서 코드가 복잡해짐
 * 2. 위 오른쪽 아래 왼쪽 순으로 비교하게 됨
 * 3. boolean 으로 체크 해서 true 일 때만 answer++
 * 4. N + 2 해서 가상의 행과 열을 만드는 방법은 좋지 않은 방법임 필요 없는 행과 열이 생기기 때문
 *
 */
public class Java_02_10_2 {

    int[] dx = {-1, 0, 1, 0};
    int[] dy = {0, 1, 0, -1};

    public int solution(int n, int[][] arr) {

        int answer = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                boolean flag = true;

                for (int k = 0; k < 4; k++) {

                    int nx = i + dx[k]; // 행 {-1, 0, 1, 0}
                    int ny = j + dy[k]; // 열 {0, 1, 0, -1} 위 오른 아래 왼 순으로 비교하게 됨

                    // 자주 실수하는 경우 arr~ 부터 한 뒤 nx ny 비교 하게 되면 IndexOutOf 가 먼저 뜨므로 순서 주의 할 것
                    // 미리 걸러줘야하는거 주의
                    if (nx >= 0 && // x 값 이동한게 0 크거나 같아야만 하고
                            nx < n && // x 값 이동한게 n 보다 작아야 한다
                            ny >= 0 && //
                            ny < n && //
                            arr[nx][ny] >= arr[i][j]) // 중심인 지점과 이동한 위치 비교
                    {

                        flag = false;
                        break; // 더 이상 확인 할 필요가 없으니 break 해서 끝냄
                    }
                }
                if (flag) answer++;
            }
        }

        return answer;
    }

    public static void main(String[] args){
        Java_02_10_2 T = new Java_02_10_2();

        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        int[][] arr = new int[n][n];

        for(int i=0; i<n; i++){
            for (int j = 0; j < n; j++) {

                arr[i][j] = kb.nextInt();
            }
        }
        System.out.print(T.solution(n, arr));
    }
}

---