자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_봉우리)

 

https://cote.inflearn.com/contest/10/problem/02-10

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

10. 봉우리

예시 입력 1 

5
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

예시 출력 1

10

 

 

내가 푼 풀이(Time: 220ms Memory: 32MB)

1. 2차원 배열의 가장자리는 모두 0이므로, 입력값 배열을 받을때 사이즈를 +2해줍니다. 그리고 인덱스 값 1부터 순회합니다.

2. 2중 for문을 사용했고, 조건문에서 열과 행을 비교하면서 가장 큰 수만 answer ++해줍니다.

3. i는 고정 값, j는 움직이는 값으로 생각하면서 풀었습니다.

import java.util.Scanner;

public class Main {
    public int solution(int n, int[][] arr){
        int answer = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int tmp = arr[i][j];
                // 첫째줄 조건은 열 체크. 둘째줄 조건은 행 체크
                if (tmp > arr[i][j+1] && tmp > arr[i][j-1]
                && tmp > arr[i+1][j] && tmp > arr[i-1][j]) {
                    answer ++;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n+2][n+2];
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.solution(n,arr));
    }
}

 

 

강의 풀이 (Time: 208ms Memory: 31MB)

1. 12시 3시 6시 9시 방향을 체크할 수 있도록 x축(행) y축(열) 배열을 만들어줍니다.

2. 방향 배열을 탐색하기 위해 for문을 3번 사용합니다.

3. 입력을 n그대로 받아서 만들었기에 가장자리에 있는 인덱스에 접근하지 않도록(ArrayIndexOutOfBoundsException안나도록) 경계선 처리를 해줍니다.

 

import java.util.Scanner;

public class Main {
    // 방향 배열을 전역으로 잡음. 스태틱이 아니라 인스턴스 배열로 잡아도 된다.
    // static인 메인 함수가 해당 배열을 접근할 일이 없고, solution만 접근할 건데,
    // solution은 객체.으로 객체를 생성해서 접근하니까 인스턴스 배열 접근할 수 있음
    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];
                    // 경계선 처리, 코드 상 실행되는게 앞쪽부터이기 때문에,
                    // arr[i][j]을 먼저 쓰면 안됨. 에러 발생하는 걸 참조해버리니까 경계선 먼저 처리
                    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) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] arr = new int[n][n];
        for (int i = 0; i < n ; i++) {
            for (int j = 0; j < n; j++) {
                arr[i][j] = sc.nextInt();
            }
        }
        System.out.println(T.solution(n,arr));
    }
}

 

 

 

커뮤니티 질문 (강사님 답변 올라오면 추후 업데이트)

 

• 경계값을 해주는걸 solution 내부 함수에서 해주는게 아니고, 입력값에서 배열 사이즈 조정하는걸로 풀면 다른 활용문제에서 어떤 문제가 발생할지 궁금합니다!
• 저는 행, 열에 각각 +1, -1 해주면서 찾았는데, 이렇게 하면 강의에서 말씀하신 대각선 값 비교할때 문제가 있을까요?
• 대각선의 경우 분기처리할때 각행과 열에 (-1, +1 ) (-1, -1) (+1, +1), (+1, -1)추가해서 체크해주는게 다른 활용 문제에서 어떤 문제가 발생할지 궁금합니다! 문제는 없지만 비효율적이고 가독성이 안좋아서 그런걸까요?
• 3중 포문으로 하면 시간복잡도가 O(n^3)가 되서 성능이 떨어지는거 아닌지 궁금합니다. 아래 코드로 하면 O(n^2)이라서 더 빠를 것 같았는데 강의로 알려주신 코드보다 12ms 더 느리더라구요!