[PS/JAVA] (배열/수학) 프로그래머스_81302_거리두기 확인하기

문제 

https://school.programmers.co.kr/learn/courses/30/lessons/81302

프로그래머스

문제 설명

 

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

1. 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
2. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
3. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예를 들어,

위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.	위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.	위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.
응시자가 앉아있는 자리(P)를 의미합니다.	빈 테이블(O)을 의미합니다.	파티션(X)을 의미합니다.

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• places의 행 길이(대기실 개수) = 5
  • places의 각 행은 하나의 대기실 구조를 나타냅니다.
• places의 열 길이(대기실 세로 길이) = 5
• places의 원소는 P,O,X로 이루어진 문자열입니다.
  • places 원소의 길이(대기실 가로 길이) = 5
  • P는 응시자가 앉아있는 자리를 의미합니다.
  • O는 빈 테이블을 의미합니다.
  • X는 파티션을 의미합니다.
• 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
• return 값 형식
  • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
  • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
  • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

---

 

입출력 예

[["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

[1, 0, 1, 1, 1]

---

입출력 예 설명

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

• (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

• 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

• 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

---

제한시간 안내

• 정확성 테스트 : 10초

※ 공지 - 2022년 4월 25일 테스트케이스가 추가되었습니다.

---

1. 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. ↩

 

 

문제에서 인사이트 도출

 

1. 문제 파악

• 거리두기의 판단 규칙은 멘하탄 거리가 2 이하인 경우로 판단한다.
• 2차원 배열에서의 원소들은 사람(P), 파티션(X), 빈 공간(0) 세가지로 구성된다.
• 멘하탄 거리가 2라는 의미는 상하좌우 방향으로 두 번 이동이 가능하다는 뜻으로 해석하자.
• 파티션의 의의는 해당 경로를 이용할 수 없다는 의미로 해석하자.
• 2차원 배열에서, 사람이 있는 곳을 검사하여, 멘하탄 거리 2 안에 접근 가능한 사람이 있는지의 여부를 체크하면 된다.

 

2. 제한사항 파악

• 입력 N의 크기는 5개의 방, 방의 크기 가로 5 세로 5로 5x5x5로 고정되어 있다.
• 4중 반복문 이상을 사용하면 1초의 시간이 초과될 확률이 있음을 인지

 

---

풀이과정 도출

 

 

1. 리팩토링 이전

아래 과정은 코드 리팩토링 하기 이전 단계이다.

 

1-1. 각 방의 배열 형태 변환 및, 2차원 배열을 순회하여 멘하튼 거리를 체크할 사람 찾아내기

 

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        char[][][] array = new char[5][9][9];
        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        // 멘하튼 거리 체크
                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}

 

1-1-1. 입력은 5x5의 2차원 배열 5개이지만, 9x9 2차원 배열 5개로 변환해주었다.

- 5x5를 파티션으로 2겹씩 감싸준 형태로 변경하였다.

- 이유는 멘하탄 거리를 체크할 때 인덱스를 초과하게 될 경우 해당 방향에는 사람이 존재하지 않고, 어차피 벽으로 막혀있으므로 파티션으로 막아두어도 된다. 또한 Out of Index 체크를 하지 않아도 된다.

 

1-1-2. 5개의 방을 순회하여,  각각의 방에서 사람이 존재하는 곳을 찾는다.

- 사람이 존재하는 곳에서 멘하튼 거리 2 내에 접근 가능한 또다른 사람이 있는지를 체크하면 된다.

 

 

---

 

1-2. 각 사람으로부터 멘하탄 거리 2 이하 다른 사람의 거리두기 여부 체크하기

 

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        char[][][] array = new char[5][9][9];
        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        //1차 상하좌우 체크
                        if(array[i][j][k+1] == 'P'
                                || array[i][j][k-1] == 'P'
                                || array[i][j+1][k] == 'P'
                                || array[i][j-1][k] == 'P'
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }                      
                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}

1-2-1. 우선 사람으로부터 상하좌우에 또다른 사람이 있는지를 체크한다.

- 바로 인접했을 경우는 멘하탄 거리 1에 해당하므로 체크해주어야 한다.

- 만약 사람이 존재할 경우 정답 배열에 거리두기를 지키지 않는다는 뜻으로 0으로 설정한 후, 나머지는 검사할 필요가 없으므로 순회를 중단하고, 다음 방의 검사를 하러 가면 된다.

		P검사
	P검사	P	P검사
		P검사

 

 

 

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        char[][][] array = new char[5][9][9];
        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        //1차 상하좌우 체크
                        if(array[i][j][k+1] == 'P'
                                || array[i][j][k-1] == 'P'
                                || array[i][j+1][k] == 'P'
                                || array[i][j-1][k] == 'P'
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }

                        //2차 멘헤튼거리2 상하좌우 체크
                        if(array[i][j][k+2] == 'P' && array[i][j][k+1] != 'X'
                                || array[i][j][k-2] == 'P' && array[i][j][k-1] != 'X'
                                || array[i][j+2][k] == 'P' && array[i][j+1][k] != 'X'
                                || array[i][j-2][k] == 'P' && array[i][j-1][k] != 'X'
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }

                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}

1-2-2. 그 다음 한 방향으로의 멘하탄 거리 2에 해당하는 거리두기 여부를 검사한다.

- 해당 방향에 멘하탄 거리 2의 사람이 있는지 검사한다.

- 해당 방향에 멘하탄 거리 1의 파티션이 없는지 검사한다.

- 만약 두 가지를 모두 만족한다면 거리두기를 지키고 있지 않는 것이다.

- 만약 멘하탄 거리 2에 사람이 있더라도, 해당 방향에 파티션이 존재한다면 거리두기를 지키고 있는 것이다.

 

		P검사
		X검사
P검사	X검사	P	X검사	P검사
		X검사
		P검사

 

 

 

 

 

 

class Solution {
    public int[] solution(String[][] places) {
        int[] answer = new int[5];

        char[][][] array = new char[5][9][9];
        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        //1차 상하좌우 체크
                        if(array[i][j][k+1] == 'P'
                                || array[i][j][k-1] == 'P'
                                || array[i][j+1][k] == 'P'
                                || array[i][j-1][k] == 'P'
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }

                        //2차 멘헤튼거리2 상하좌우 체크
                        if(array[i][j][k+2] == 'P' && array[i][j][k+1] != 'X'
                                || array[i][j][k-2] == 'P' && array[i][j][k-1] != 'X'
                                || array[i][j+2][k] == 'P' && array[i][j+1][k] != 'X'
                                || array[i][j-2][k] == 'P' && array[i][j-1][k] != 'X'
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }

                        //3차 대각 체크
                        if(array[i][j+1][k+1] == 'P' && (array[i][j][k+1] != 'X' || array[i][j+1][k] != 'X')
                                || array[i][j+1][k-1] == 'P' && (array[i][j][k-1] != 'X' || array[i][j+1][k] != 'X')
                                || array[i][j-1][k+1] == 'P' && (array[i][j][k+1] != 'X' || array[i][j-1][k] != 'X')
                                || array[i][j-1][k-1] == 'P' && (array[i][j][k-1] != 'X' || array[i][j-1][k] != 'X')
                        ){
                            answer[i] = 0;
                            break roomLoop;
                        }
                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}

1-2-3. 마지막으로 대각선의 사람의 거리두기 여부를 검사한다.

- 대각선에 사람이 있는지를 검사한다.

- 해당 대각선으로 접근 가능한 경로에 파티션이 하나라도 존재하지 않는지의 여부를 검사한다.

- 만약 두 가지를 모두 만족한다면 거리두기를 지키고 있지 않는 것이다.

 

 

	P검사		P검사
		P
	P검사		P검사

 

	P검사	X검사
	X검사	P

 

 

---

 

 

2. 리팩토링 이후

 

위 코드로도 분명 문제없이 거리두기 문제의 해답을 도출하는 것이 가능하다. 다만 위 과정에서는 상하좌우 / 2거리의 상하좌우 / 대각을 각각 검사하게 되어, 불필요한 연산이 포함되어 있다는 사실이다.

 

사실 위 방법은 후보군 칸에 거리두기를 지키지 않은 사람의 유무를 위주로 생각하여 알고리즘을 생각했다고 보면 된다.

사실 아래처럼 후보군 칸에 접근이 가능한지의 여부를 통해서 알고리즘을 짜는 쪽이 효율적이다.

 

		↑(2)
	←(2)	↑(1)	→(2)
		P

다음 그림과 같이 멘하탄 거리 1에 해당하는 한 방향 씩 검사한 후, (1)에 무엇이 있는지에 따라 아래의 행동을 취하면 된다.

1. P(사람)인 경우 : 거리두기를 지키지 않음으로 판단하고 중단

2. X(파티션)인 경우 : (2) 후보군으로 접근이 불가능하므로 해당 방향은 거리두기를 지킴으로 판단하고 중단

3. 0(빈 공간)인 경우 : (2) 후보군에 사람이 있는지의 여부를 체크하여 거리두기를 하지 않는지를 가지를 뻗어 검사

 

다음 행동을 네 방향 모두에 대해서 취하면 된다.

 

 

---

 

2-1. 거리를 표현하는 dx, dy 사용하기

//1차 상하좌우 체크
if(array[i][j][k+1] == 'P'
        || array[i][j][k-1] == 'P'
        || array[i][j+1][k] == 'P'
        || array[i][j-1][k] == 'P'
){
    answer[i] = 0;
    break roomLoop;
}

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

//1차 상하좌우 체크
for(int l = 0; l < 4; l++){
	int px = k + dx[l];
	int py = j + dy[l];
        if(array[i][py][px] == 'P') {
            answer[i] = 0;
            break roomLoop;
        }
}

2-1-1. 방향을 나타내는 변수로 dx, dy를 이용할 수 있다.

- 기존 상하좌우에 대한 인덱스를 직접 조작하여 총 4번의 코드를 작성해야 하는 것을, dx, dy 방향변수를 사용하여 변경할 수 있다.

- 방향은 상/하/좌/우 총 4가지의 경우가 있으며 각각의 방향변수는 4가지 경우에 대한 x로 이동해야 하는 인덱스와 y로 이동해야 하는 인덱스를 표현한다.

- 따라서 반복문을 이용하여, 코드 작성을 간소화할 수 있고, 실수를 방지할 수 있다.

 

 

 

 

 

2-2. 상하좌우 멘하탄 거리 1에 대한 거리두기 여부 검사하기

class Solution {
    int[] answer = new int[5];
    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, -1, 1, 0};

    char[][][] array = new char[5][9][9];

    public boolean check(int i, int y, int x){
        for(int l = 0; l < 4; l++){
            int px = x + dx[l];
            int py = y + dy[l];
            if(array[i][py][px] == 'P'){
                return false;
            }
            else if(array[i][py][px] == 'O')
            {
                // (2) 멘하탄 거리 2에 해당하는 의심후보군들 검사하기
            }
        }
        return true;
    }
    public int[] solution(String[][] places) {

        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        if(check(i, j, k) == false){
                            answer[i] = 0;
                            break roomLoop;
                        }
                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}

2-2-1. check 함수 선언

- 이제 멘하탄 거리 1인 곳을 검사하고, 그곳을 기점으로 멘하탄 거리 2인 곳을 뻗어나가 검사할 것이므로, 함수를 통해 멘하탄 거리 1인 곳을 검사하는 로직을 구현하였다.

- 상하좌우에 있는 원소를 검사하고, 사람일 경우에는 거리두기를 지키지 않는 것으로 판단, 빈 공간일 경우 멘하탄 거리 2에 해당하는 곳에 사람이 있는지를 검사할 수 있도록 작성한다.

 

 

 

 

 

2-3. 멘하탄 거리 2에 대한 거리두기 여부 가지뻗어 검사하기

class Solution {
    int[] answer = new int[5];
    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, -1, 1, 0};

    char[][][] array = new char[5][9][9];

    public boolean check_inner(int i, int y, int x, int originX, int originY){
        for(int l = 0; l < 4; l++){
            int px = x + dx[l];
            int py = y + dy[l];
            if(px == originX && py == originY){
                continue;
            }
            if(array[i][py][px] == 'P'){
                answer[i] = 0;
                return false;
            }
        }
        return true;
    }

    public boolean check(int i, int y, int x){
        for(int l = 0; l < 4; l++){
            int px = x + dx[l];
            int py = y + dy[l];
            if(array[i][py][px] == 'P'){
                return false;
            }
            else if(array[i][py][px] == 'O')
            {
                if(check_inner(i, py, px, x, y) == false){
                    return false;
                }
            }
        }
        return true;
    }
    public int[] solution(String[][] places) {

        //...
        
    }
}

 

2-3-1. check_inner 함수 선언

- 멘하탄 거리가 1인 곳에서, 빈 공간일 경우 check_inner 함수를 이용하여 뻗어나가 멘하탄 거리가 2인 곳을 검사하는 로직을 추가한다.

- 이동한 인덱스를 시점으로 한번 더 상하좌우에 사람(P)가 있는지의 여부를 검사한다.

 

 

2-3-2. 검사 방향 예외

- 단, 원래 검사를 시작했던 곳으로는 검사를 진행하면 안 된다.

- 예를 들어 위쪽 방향 -> 좌/상/우 방향 검사만 이루어져야 하고, 위쪽 방향 -> 하단 방향으로는 검사가 이루어져서는 안 된다.

- 따라서 함수에, 원래 검사를 시작했던 사람의 인덱스를 함께 넘겨, 해당 방향은 검사를 진행하지 않도록 코드를 추가해주어야 한다.

 

 

 

---

최종 소스코드

 

class Solution {
    int[] answer = new int[5];
    int[] dx = {-1, 0, 0, 1};
    int[] dy = {0, -1, 1, 0};

    char[][][] array = new char[5][9][9];

    public boolean check_inner(int i, int y, int x, int originX, int originY){
        for(int l = 0; l < 4; l++){
            int px = x + dx[l];
            int py = y + dy[l];
            if(px == originX && py == originY){
                continue;
            }
            if(array[i][py][px] == 'P'){
                answer[i] = 0;
                return false;
            }
        }
        return true;
    }

    public boolean check(int i, int y, int x){
        for(int l = 0; l < 4; l++){
            int px = x + dx[l];
            int py = y + dy[l];
            if(array[i][py][px] == 'P'){
                return false;
            }
            else if(array[i][py][px] == 'O')
            {
                if(check_inner(i, py, px, x, y) == false){
                    return false;
                }
            }
        }
        return true;
    }
    public int[] solution(String[][] places) {

        for(int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                array[i][j] = new char[]{'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X', 'X'};
                if (!(j < 2 || j > 6)) {
                    char[] line = places[i][j - 2].toCharArray();
                    System.arraycopy(line, 0, array[i][j], 2, 5);
                }

            }
        }
        for(int i = 0; i < 5; i++){

            roomLoop : for(int j = 2; j < 7; j++){
                for(int k = 2; k < 7; k++){
                    if(array[i][j][k] == 'P'){
                        if(check(i, j, k) == false){
                            answer[i] = 0;
                            break roomLoop;
                        }
                    }
                }
                answer[i] = 1;
            }

        }

        return answer;
    }
}