[코딩테스트][프로그래머스] "거리두기 확인하기" 완벽 공략: Python과 Java로 문제 해결하기!

문제 설명

프로그래머스 거리두기 확인하기 문제

Python 풀이

def check_board(board, people):
    numOfPeople = len(people)
    for i in range(numOfPeople - 1):
        for j in range(i + 1, numOfPeople):
            x1, y1 = people[i]
            x2, y2 = people[j]
            dist = abs(x1 - x2) + abs(y1 - y2)
            if dist > 2:
                continue
            elif dist < 2:
                return False
            else:
                if abs(x1 - x2) == 0:
                    if board[x1][(y1 + y2) // 2] != 'X':
                        return False
                elif abs(y1 - y2) == 0:
                    if board[(x1 + x2) // 2][y1] != 'X':
                        return False
                elif abs(x1 - x2) == 1 and abs(y1 - y2) == 1:
                    if board[x1][y2] != 'X' or board[x2][y1] != 'X':
                        return False
    return True

def solution(places):
    answer = []
    for tc in range(5):
        case = places[tc]
        board = []
        people = []
        for i in range(5):
            tmp = case[i]
            for j in range(5):
                if tmp[j] == 'P':
                    people.append((i, j))
            board.append(list(tmp))
        if check_board(board, people):
            answer.append(1)
        else:
            answer.append(0)
    return answer

Java 풀이

import java.util.*;

class Solution {
    public static boolean check(String[][] board, List<int[]> people) {
        int numOfPeople = people.size();
        for (int i = 0; i < numOfPeople - 1; i++) {
            int x1 = people.get(i)[0];
            int y1 = people.get(i)[1];
            for (int j = i + 1; j < numOfPeople; j++) {
                int x2 = people.get(j)[0];
                int y2 = people.get(j)[1];
                int dist = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                if (dist > 2) {
                    continue;
                } else if (dist < 2) {
                    return false;
                } else {
                    if (x1 == x2) {
                        if (!board[x1][(y1 + y2) / 2].equals("X")) {
                            return false;
                        }
                    } else if (y1 == y2) {
                        if (!board[(x1 + x2) / 2][y1].equals("X")) {
                            return false;
                        }
                    } else if (Math.abs(x1 - x2) == 1 && Math.abs(y1 - y2) == 1) {
                        if (!board[x1][y2].equals("X") || !board[x2][y1].equals("X")) {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public int[] solution(String[][] places) {
        int[] answer = new int[5];
        for (int tc = 0; tc < 5; tc++) {
            String[] k = places[tc];
            String[][] board = new String[5][5];
            List<int[]> people = new ArrayList<>();
            for (int i = 0; i < 5; i++) {
                String[] tmp = k[i].split("");
                for (int j = 0; j < 5; j++) {
                    if (tmp[j].equals("P")) {
                        people.add(new int[]{i, j});
                    }
                }
                board[i] = tmp;
            }
            if (check(board, people)) {
                answer[tc] = 1;
            }
        }
        return answer;
    }
}

내 생각

• Python 풀이시간: 45분
• Java 풀이시간: 30분

각 5개의 케이스에 관해서 일단 반복문으로 구분을 둔다. 그런 후 board를 2차원 배열을 두어 완성시키면서 한 줄에 대해서 P가 있을 경우, 해당 좌표를 나중에 사람 간의 거리와 맨해튼 거리를 확인하기 위해 따로 저장해 둔다. 이렇게 두 개를 통해 통과와 불통의 과정을 함수로 만들어두고 통과할 시 1을, 통과 못할 시 0을 저장하면 된다.

함수에서는 각 사람 간을 한 명씩 비교 대조하면서 거리를 구하고 벽이 막고 있는지 확인하면 된다. 거리가 2보다 클 경우는 무조건 통과이고, 2보다 작은 경우는 무조건 불통이다. 그리고 거리가 2인 경우만 확인하면 되는데 이때는 세로축으로 2인 경우, 가로축으로 2인 경우, 대각선으로 2인 경우를 나누어서 비교하면 된다. 가로나 세로로 2인 경우에는 가운데 벽이 있으면 통과이고, 그렇지 않으면 전부 불통이다. 대각선으로 2인 경우에는 두 점을 기준으로 사각형을 그렸을 때 두 점을 제외한 좌표가 벽인 경우와 같으므로 나머지 두 좌표가 벽인지 확인해주면 된다.