문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,
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을 담습니다.
입출력 예
places | result |
[["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초
- 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다. ↩
풀이 방법 생각
먼저 대기실에 있는 사람 위치를 구한 후 사람 간의 간격을 구해서 맨해튼 거리가 2 이하인 사람 쌍을 구했다. 그리고 사람 쌍별로 사이에 파티션이 있는지 없는지 확인하는 방법을 생각했다.
person이 사람 위치가 들어있는 list이고, Manhattan이 맨해튼 거리가 2이하인 사람 쌍이 들어있는 list이다.
사람 쌍에서 x 좌표 값이 같으면 y값이 작은 좌표 값에 1을 더해 O 또는 P 로 확인 되면 맨해튼 거리를 지키지 않는다고 판단했다. O 과 P 둘 다 고려한 이유는 맨해튼 거리가 2이하인 것으로 구했기 때문에 1이면 바로 아래 사람이 있기 때문이다. y 좌표 값이 같을 경우는 반대로 하면 되고 대각에 있는 경우는 두 사람의 x, y 좌표를 교차로 바꾸게 되면 확인할 2군데가 나오기 때문에 그 좌표들을 확인해서 맨해튼 거리를 지키지 않는지 판단했다.
내 코드
import java.awt.*;
import java.util.ArrayList;
class Solution {
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
for (int k = 0; k < places.length; k++) {
int keepDistance = 1;
ArrayList<Point> person = new ArrayList<>();
ArrayList<Point[]> Manhattan = new ArrayList<>();
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (places[k][i].charAt(j) == 'P') {
person.add(new Point(i, j));
}
}
}
if (person.size() >= 2) {
for (int i = 0; i < person.size() - 1; i++) {
for (int j = i + 1; j < person.size(); j++) {
if (Math.abs(person.get(i).getX() - person.get(j).getX()) + Math.abs(person.get(i).getY() - person.get(j).getY()) <= 2) {
Point p1 = new Point((int) person.get(i).getX(), (int) person.get(i).getY());
Point p2 = new Point((int) person.get(j).getX(), (int) person.get(j).getY());
Manhattan.add(new Point[]{p1, p2});
}
}
}
}
if (!Manhattan.isEmpty()) {
for (int i = 0; i < Manhattan.size(); i++) {
if (Manhattan.get(i)[0].getX() == Manhattan.get(i)[1].getX()) {
if (places[k][(int) Manhattan.get(i)[0].getX()].charAt((int) Manhattan.get(i)[0].getY() + 1) == 'O' || places[k][(int) Manhattan.get(i)[0].getX()].charAt((int) Manhattan.get(i)[0].getY() + 1) == 'P') {
keepDistance = 0;
break;
}
} else if (Manhattan.get(i)[0].getY() == Manhattan.get(i)[1].getY()) {
if (places[k][(int) Manhattan.get(i)[0].getX() + 1].charAt((int) Manhattan.get(i)[0].getY()) == 'O' || places[k][(int) Manhattan.get(i)[0].getX() + 1].charAt((int) Manhattan.get(i)[0].getY()) == 'P') {
keepDistance = 0;
break;
}
} else {
if (places[k][(int) Manhattan.get(i)[0].getX()].charAt((int) Manhattan.get(i)[1].getY()) == 'O' || places[k][(int) Manhattan.get(i)[1].getX()].charAt((int) Manhattan.get(i)[0].getY()) == 'O') {
keepDistance = 0;
break;
}
}
}
}
answer[k] = keepDistance;
}
return answer;
}
}
다른 사람 풀이
class Solution {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static boolean[][] visit;
static int[] answer;
public void dfs(int num, int x, int y, int count, String[] places){
if (count > 2) return;
if (count > 0 && count <= 2 && places[x].charAt(y) == 'P'){
//2칸 범위내에 다른 응시자가 있을 경우 거리두기 미준수로 0처리
answer[num] = 0;
return;
}
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//배열 범위 밖으로 초과하는지 여부 검사, 파티션으로 분리되어 있는 경우 상관 없음.
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && places[nx].charAt(ny) != 'X') {
if (visit[nx][ny]) continue; //이미 방문한 곳일 경우 생략
visit[nx][ny] = true;
dfs(num, nx, ny, count + 1, places);
visit[nx][ny] = false;
}
}
}
public int[] solution(String[][] places) {
answer = new int[places.length];
for (int i = 0; i < places.length; i++) {
answer[i] = 1;
}
for (int i = 0; i < places.length; i++) {
visit = new boolean[5][5];
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 5; k++) {
if (places[i][j].charAt(k) == 'P'){
visit[j][k] = true;
dfs(i, j, k, 0, places[i]);
visit[j][k] = false;
}
}
}
}
return answer;
}
}
dfs 를 이용한 풀이이다. dfs 메소드에서 num은 대기실 순서, x 와 y 는 좌표, count는 맨해튼 거리를 나타내고, places는 대기실 배열이다.
일단 count가 2보다 크면 해당되지 않기 때문에 return 해준다. count가 0에서 2 사이이고 P이면 return 하고 0을 answer[num]에 저장한다. return 되지 않았다면 상하좌우를 확인해서 대기실 범위안에 들어있고 X가 아닌 좌표 중 방문하지 않은 좌표를 count+1해서 dfs를 한다. dfs는 상하좌우만 확인하게 되면 다음 상하좌우를 확인할 때 대각선도 확인되기 때문에 따로 대각을 확인할 필요가 없다.
대각을 확인할 필요가 없다는 생각과 dfs로 접근할 생각을 하지 못했었다. 성능도 좋고 풀이도 깔끔한 좋은 코드로 생각된다.
'코딩테스트 > [프로그래머스] 코딩테스트 연습' 카테고리의 다른 글
메뉴 리뉴얼 (0) | 2021.08.08 |
---|---|
숫자 문자열과 영단어 (0) | 2021.08.07 |
행렬 테두리 회전하기 (0) | 2021.08.04 |
로또의 최고 순위와 최저 순위 (0) | 2021.08.03 |
부족한 금액 계산하기 (0) | 2021.08.03 |