프로그래머스 : 양옆앞뒤 큰 수 찾기

오늘은 알고리즘 테스트 시험을 봤다.

난이도 상, 중, 하 이렇게 세문제가 나왔으나 중, 하는 쉬웠다.

하지만 난이도가 상인 문제는 어려웠다.

상하좌우의 값을 비교해 가장 큰 값이라면 별을 출력하게 해야 하는 문제였다

처음에는 배열초과가 일어나지 않게 하기 위해 총 세부분으로 나누어 작업했다

1. 두 부분의 값만 비교하면 되는 꼭짓점

2. 세 부분의 값만 비교하면 되는 모서리

3. 상하좌우 모두 비교하여야 하는 안쪽 부분

public class Test_3 {
    public void Solution(int[][] checkin){
        String [][] answer = new String[checkin.length][checkin[0].length];

        // 1 꼭짓점 부분 구현
        // 1-1. [0, 0]
        answer[0][0] = (checkin[0][0] > Math.max(checkin[0][1], checkin[1][0])
                ? "*" : String.valueOf(checkin[0][0]));
        
        // 1-2 [0, max]....


        // 2. 세가지 값만 비교하면 되는 모서리 부분 구현
        for(int i = 1; i < checkin.length-1; i++) {

            //첫번째 열
            answer[0][i] = (checkin[0][i]
                    > Math.max(checkin[1][i]
                        , Math.max(checkin[0][i - 1], checkin[0][i + 1])))
                    ? "*" : String.valueOf(checkin[0][i]);
			
            //마지막 열 ....
           
           
        // 3. 상하좌우를 모두 비교해야 하는 두번째 ~ 마지막 앞까지의 행과 열
        for(int i = 1; i < checkin.length-1; i++){
            for(int j = 1; j < checkin[i].length-1; j++){
                answer[i][j] = (checkin[i][j] >
                        Math.max(
                                Math.max(checkin[i][j-1], checkin[i][j+1]),
                                Math.max(checkin[i-1][j], checkin[i+1][j])))
                        ? "*" : String.valueOf(checkin[i][j]);
            }
        }

이렇게 푸는 문제가 아니란걸 문제를 풀면서도 확신했다.

어쨌든 올바르게 동작하기에 제출을 하고 난 후 어떻게 푸는 게 효율적인지 찾아보니

방향벡터(Directional Vector) 방식을 이용하여 푸는 문제라고 한다.   

방향벡터는 특정 방향을 나타내기 위해 사용되며 (x, y) 형태로 표현한다.

예를 들어 (1, 0)은 x축으로만 1만큼, (0, -1)은 y축으로만  -1만큼 이동함을 나타낸다.

 

코드로 작성해봤다.

                    //상 우 하 좌
int[][] direction = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

     // *을 넣기위해 max값 확인을 위한 boolean
     boolean isMaxValue = true;

     for (int i = 0; i < 4; i++) {
     int dx = x + direction[i][0], dy = y + direction[i][1];

     // 상, 하, 좌, 우 배열을 초과하는 위치가 있는 경우 continue;
     if (dx < 0 || dx >= 5 || dy < 0 || dy >= 5) {
         continue;
     }

     // 상, 하, 좌, 우 크거나 같은 값이 있는 경우 isMaxValue를 false로 반환
     if (checkin[x][y] <= checkin[dx][dy]) {
     	isMaxValue = false;
        break;
        }
    }
     answer[x][y] = (isMaxValue)? "*" : String.valueOf(checkin[x][y]);

오늘 테스트로 방향벡터를 직접 구현해 봄으로써 어떤 원리로 동작하는지, 어떤 상황에 사용해야 할지 알 수 있었다.