[PCCP 대비] ch 3 배열 (2)

문제 3) 거리두기 확인하기 

 

코딩테스트 연습 - 거리두기 확인하기 | 프로그래머스 스쿨

프로그래머스

 

 

● 문제 풀이 

 

- 단순히 상하좌우를 확인하는 것이 아니라 맨해튼 거리가 2인 모든 위치를 확인해야 한다. 

- 맨해튼 거리 2 내에 파티션이 사이에 있지 않은 다른 응시자가 있는지 검사해야 한다.

- 주목할 점은 맨해튼 거리 2에 도달하려면 먼저 맨해튼 거리 1(상하좌우)을 거쳐야 한다는 것이다. 

 

- 맨해튼 거리 2인 위치에 도달하려면 맨해튼 거리 1인 위치를 거쳐야 하고, 맨해튼 거리 1의 위치들이 파티션으로 막혀 있다면 맨해튼 거리 2에는 다른 응시자가 있어도 파티션에 가로막히기 때문에 거리두기가 인정된다. 

 

- 어떤 방향이 막혀 있다면 그 방향을 통하는 위치들을 배제하는 것이 아니라, 어떤 방향이 뚫려 있다면 그 방향을 검사하도록 해야 한다. 

 

맨해튼 거리 2 검사 과정 

 

-> 검사 위치 (x,y)에서 위쪽으로 진행했을 때 파티션이 가로막고 있다. 이 파티션을 통과해서 도달하는 맨해튼 거리 2 위치들은 의미가 없기 때문에 추가 검사를 하지 않고 다음 방향으로 넘어간다. 

 

-> 다음 방향인 오른쪽으로 진행했을 때는 빈 테이블이 있다. 빈 테이블을 통해 다른 응시자에게 도달하면 거리두기를 지키지 않은 것이므로 빈 테이블과 연결된 맨해튼 거리 2 위치들을 검사해야 한다. 

 

문제 풀이 흐름 

 

하나의 대기실에 대한 문제 풀이 흐름 

 

1. 대기실의 모든 응시자 위치에 대해 반복

    A. 상하좌우 중 빈 테이블이 있는 방향에 대해 1-B로 진행

    B. 빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기를 지키지 않은 것

 

2. 모든 응시자의 위치를 검사했으나 거리두기를 지키지 않은 경우를 발견하지 못했으면 거리 두기를 지킨 것

 

 

코드 작성 

 

- 입력되는 데이터를 문제 풀이 흐름에 맞게 가공

- 입력이 String[ ][ ] 형식으로 들어오고, 대기실 하나는 String[ ] 형식이 된다. 

- 원소 하나한에 관심이 있고 각 대기실이 거리두기를 지키는지 검사할 것이므로 대기실을 char[ ][ ] 형식으로 만들어 주고, 거리두기 결과를 저장할 배열을 선언한다. 

 

 int[] answer = new int[places.length];
        
        for(int i=0; i<answer.length; i++) {
            String[] place = places[i];
            char[][] room = new char[place.length][];
            
            for(int j=0; j<room.length; j++) {
                room[j] = place[j].toCharArray();
            }
            
            //거리두기 검사 후 answer에 기록
        }
        
        return answer;

 

 

- 하나의 대기실은 char[ ][ ]로 표현되었다. 이 대기실이 거리두기를 지키고 있는지 검사하는 isDistanced() 메서드를 다음과 같이 선언한다. 

- isDistanced() 메서드 안에서 문제 풀이 흐름을 구현할 수 있다. 

 

private boolean isDistanced(char[][] room) {
       //거리두기 검사 
       return true;
}

 

 

1. 대기실의 모든 응시자 위치에 대해 반복 

 

- 대기실에서 응시자가 앉아 있는 모든 위치에 대해 거리두기 검사를 진행해야 한다. 다음과 같이 응시자가 앉아 있지 않은 위치들은 continue; 키워드로 검사를 건너뛰도록 한다. 

 

for(int y=0; y<room.length; y++) {
   for(int x=0; x<room[y].length; x++) {
       if(room[y][x] != 'P') continue;
       //거리두기 검사 
   }
}

 

- 해당 대기실에서 응시자의 위치 (x,y)가 거리두기를 지키는지 검사하는 메서드를 선언 

//해당 대기실에서 (x,y)위치의 응시자가 거리두기를 지키고 있는지 검사 
private boolean isDistanced(char[][]room, int x, int y) {
    //room[y][x]가 거리두기를 지키는지 검사 
    return true;
}

 

 

1-A. 상하좌우 중 빈테이블이 있는 방향에 대해 1-B로 진행

 

 

- (x,y) 위치에 있는 응시자가 거리두기를 지키고 있는지 검사하려면 먼저 상하좌우를 검사해야 한다. 상하좌우를 검색하고자 다음과 같이 dx,dy를 선언해준다. 

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

 

- 다음과 같이 상하좌우 위치를 가져오고, 해당 위치가 범위를 벗어나지 않는지 검사한다. 

for(int d=0; d<4; d++) {
     int nx = x +dx[d];
     int ny = y +dy[d];
            
     if(ny<0 || ny>=room.length || nx <0 || nx>=room.length)
         continue;
 }

 

-  room[ny][nx]의 값의 의미를 switch문으로 구현 

X : 파티션	이 위치를 이용하여 다른 응시자에게 도달할 수 없으므로 별도의 처리가 필요하지 않음
P : 응시자	맨해튼 거리 1에 다른 응시자가 있는 것이므로 거리두기가 지켜지지 않은 것
O : 빈 테이블	인접한 곳에 다른 응시자가 있다면 거리두기가 지켜지지 않은 것

 

switch(room[ny][nx]) {
    case 'P' : return false;
    case 'O':
        //인접한 곳에 다른 응시자가 있는지 검사
        break;
}

 

 

1-B. 빈 테이블과 인접한 위치 중 응시자가 있다면 거리두기를 지키지 않은 것

 

 

- 여기서 인접한 곳이라 함은 다시 상하좌우를 의미한다 하지만 원래 검사를 시작했던 응시자는 제외해야 하기 때문에 해당 방향으로는 검사를 시행하지 않아야 한다. 

 

맨해튼 거리 1 위치에서 검사방향 

 

 

- 따라서 검사를 제외할 방향도 함께 넣어주어야 한다. exlude 방향을 제외한 네 방향에 다른 응시자가 있는지 검사하는 isNextToVolunteer() 메서드를 다음과 같이 정의한다. 

 

//exclude 방향을 제외한 네 방향에 다른 응시자가 있는지 검사 
private boolean isNextToVolunteer(char[][] room, int x, int y, int exclude) {
    for(int d=0; d<4; d++) {
        if(d==exclude) continue;
            
        int nx = x + dx[d];
        int ny = y + dy[d];
            
        if(ny<0 || ny >= room.length || nx < 0 || nx >= room[ny].length) continue;
        if(room[ny][nx] == 'P') return true;
            
    }
    return false;
}

 

 

- isDistanced(room,x,y) 메서드에서 알고 있는 정보는 (x,y)에서의 진행 방향 정보이다. 우리가 제외해야 할 것은 그 반대 방향이므로 방향 d를 이용하여 반대방향 exclude를 계산해야 한다. 

 

- 상좌우하 방향으로 dx,dy를 수정한다. 이렇게 하면 방향 인덱스가 상-0, 하-3, 좌-1, 우-2가 된다. 반대 방향 인덱스끼리 더하면 3이 됨을 알 수 있다. 

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

 

- 이를 이용하여 다음과 같이 isDistanced(room,x,y) 메서드의 switch 문을 완성한다. 

switch(room[ny][nx]) {
     case 'P' : return false;
     case 'O':
         if(isNextToVolunteer(room,nx,ny,3-d)) return false;
         break;
 }

 

- 특정 위치의 응시자가 거리두기를 지키는지 검사할 수 있게 되었으니 대기실 전체가 거리두기를 지키는지 검사하는 isDistanced(room) 메서드도 다음과 같이 완성할 수 있다. 

 

private boolean isDistanced(char[][] room) {
        for(int y=0; y<room.length; y++) {
            for(int x=0; x<room[y].length; x++) {
                if(room[y][x] != 'P') continue;
                if(!isDistanced(room,x,y)) return false;
            }
        }       
        return true;
}

 

 

전체 코드 

 

class Solution {
    
    // 상좌우하 
    private static final int dx[] = {0, -1, 1, 0};
    private static final int dy[] = {-1, 0, 0, 1};
    
    // 해당 대기실이 거리두기를 지키고 있는지 검사 
    private boolean isDistanced(char[][] room) {
        for (int y = 0; y < room.length; y++) {
            for (int x = 0; x < room[y].length; x++) {
                if (room[y][x] != 'P') continue;
                if (!isDistanced(room, x, y)) return false;
            }
        }
        return true;
    }
    
    // 해당 대기실에서 (x,y)위치의 응시자가 거리두기를 지키고 있는지 검사 
    private boolean isDistanced(char[][] room, int x, int y) {
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if (ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) 
                continue;
            
            // Move the switch inside the loop
            switch (room[ny][nx]) {
                case 'P':
                    return false;
                case 'O':
                    if (isNextToVolunteer(room, nx, ny, 3 - d)) return false;
                    break;
            }
        }
        return true;
    }

    // exclude 방향을 제외한 네 방향에 다른 응시자가 있는지 검사 
    private boolean isNextToVolunteer(char[][] room, int x, int y, int exclude) {
        for (int d = 0; d < 4; d++) {
            if (d == exclude) continue;
            
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if (ny < 0 || ny >= room.length || nx < 0 || nx >= room[ny].length) 
                continue;
            
            if (room[ny][nx] == 'P') return true;
        }
        return false;
    }
    
    public int[] solution(String[][] places) {
        int[] answer = new int[places.length];
        
        for (int i = 0; i < answer.length; i++) {
            String[] place = places[i];
            char[][] room = new char[place.length][];
            
            for (int j = 0; j < room.length; j++) {
                room[j] = place[j].toCharArray();
            }
            
            // 거리두기 검사 후 answer에 기록
            if (isDistanced(room)) {
                answer[i] = 1;
            } else {
                answer[i] = 0;
            }
        }
        return answer;
    }
}

 

 

3) 연산 

 

- 2차원 배열은 평면뿐만 아니라 중첩된 데이터나 행렬을 표현하는 데도 많이 사용된다. 

 

 

문제 4) 행렬의 곱셈 

 

코딩테스트 연습 - 행렬의 곱셈 | 프로그래머스 스쿨

프로그래머스

 

 

● 문제 풀이 

 

- 행렬의 곱셈은 왼쪽 행렬의 행과 오른쪽 행렬의 열이 짝을 이루어 수행한다. 

- 왼쪽 행렬은 행 단위로 오른쪽 행렬은 열 단위로 계산되며 같은 순서에 있는 숫자끼리 곱해서 모두 더하면 된다. 

- 행렬의 곱셈 결과는 또 다른 행렬이 된다. 

 

- 결과 행렬은 다음과 같이 선언 가능하다. 

int[][] arr = new int[arr1.length][arr2[0].length];
//행렬 곱셈
return arr;

 

- 행렬의 곱셈 결과는 곱해지는 두 행렬의 행과 열을 순회하면서 곱한 값들을 모두 더해주어야 한다. 

 arr[i][j] = 0;
 for(int k=0; k<arr1[i].length; k++) {
     arr[i][j] +=arr1[i][k] * arr2[k][j];
 }

 

 

전체 코드 

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] arr = new int[arr1.length][arr2[0].length];
        
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                arr[i][j] = 0;
                for(int k=0; k<arr1[i].length; k++) {
                    arr[i][j] +=arr1[i][k] * arr2[k][j];
                }
            }
        }
        
        return arr;
    }
}