[알고리즘] 배열(10) : 봉우리(JAVA)

문제

풀이

문제를 보고 든 생각은 n값을 입력받고
문제를 풀때 n의 값을 입력받고, 0행과 n-1행의 값을 0 으로 설정
0열과 n-1열의 값을 0으로 설정한 후,

2중 for문을 이용해 상하좌우의 값을 비교한후 카운팅 하려고했다.

하지만 방향이 8개인 경우에는??

위와 같은 질문에 답을 하려면 방향이 8개가 필요하다는 결론이 나온다.

이 문제는 해결을 하지 못했기 때문에 해답을 보았다.

소스코드

package algolecture;

import java.util.Scanner;

public class Main22 {
    int[] dx = {-1,0,1,0};
    int[] dy = {0,1,0,-1};
    // dx,dy는 전역변수!
    // 인스턴스 배열로 잡아도 상관없다.
    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];
                    int ny = j+dy[k];
                    if(nx>= 0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]){
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    answer++;
            }
        }
        return answer;
    }
    // 경계선 처리도 해줘야 한다.


    public static void main(String[] args) {
        Main22 T = new Main22();
        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));
    }
}

🥇 소스코드 분석

main 메소드

Scanner를 통해 정수 값(n)을 입력 받고, n의 크기만큼의 2중배열을 만들어 준다.
Scanner의 nextInt()를 통해 값을 입력받는다.

System.out.println(T.solution(n, arr));

• Main22 의 객체인 T의 solution메소드를 이용해 값을 출력한다.

solution 메소드

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

• public필드이고 int형을 반환한다. 매개변수는 main메소드에서 입력받은 n, int[][] arr 이다.

• boolean flag = true; flag의 값을 참으로 선언한다.

• Main클래스의 전역변수 dx, dy의 값을 for문을 이용해 상하좌우의 인덱스 번호를 출력한다.

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];
        	int ny = j + dy[k];
          	if(arr[nx][ny] >= arr[i][j]){
            	flag = false;
                break;
            }
       	}
        if(flag)
        	answer++;
    }
}
	return answer;
}

위와 같이 하나씩 다 검색을 하지 않고 nx, ny를 이용해서 답을 구할 수 있다.

하지만 위의 답은 틀린 답이다. 왜나하면 n값을 5라고 입력했을때 배열의 형태는

[0][0] [0][1] [0][2] [0][3] [0][4] 
[1][0] [1][1] [1][2] [1][3] [1][4]
[2][0] [2][1] [2][2] [2][3] [2][4]
[3][0] [3][1] [3][2] [3][3] [3][4]
[4][0] [4][1] [4][2] [4][3] [4][4] 

위와 같은 형식이 되는데, nx의 값이 -1이 되는 경우도 있기 때문이다. 따라서 다음과 같은 조건을 추가해 줘야한다.

if(nx >= 0 && nx<n && ny>=0 && ny<n && arr[nx][ny] > arr[i][j])

완성된 코드를 다시 보자!

package algolecture;

import java.util.Scanner;

public class Main22 {
    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];
                    int ny = j+dy[k];
                    if(nx>= 0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]){
                        flag = false;
                        break;
                    }
                }
                if(flag)
                    answer++;
            }
        }
        return answer;
    }
    // 경계선 처리도 해줘야 한다.


    public static void main(String[] args) {
        Main22 T = new Main22();
        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));
    }
}