문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 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을 담습니다.
입출력 예 설명
나의 풀이
import java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
for (int i = 0; i < places.length; i++) {
String[] p = places[i];
boolean isOk = true;
for (int r = 0; r < 5 && isOk; r++) {
for (int c = 0; c < 5 && isOk; c++) {
if (p[r].charAt(c) == 'P') {
if (!bfs(r, c, p))
isOk = false;
}
}
}
answer[i] = isOk ? 1 : 0;
}
return answer;
}
private static boolean bfs(int r, int c, String[] p) {
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, -1, 1 };
Queue<int[]> queue = new LinkedList<int[]>();
queue.offer(new int[] { r, c });
while (!queue.isEmpty()) {
int[] position = queue.poll();
for (int i = 0; i < 4; i++) {
int nr = position[0] + dr[i];
int nc = position[1] + dc[i];
if (nr < 0 || nc < 0 || nr >= 5 || nc >= 5 || (nr == r && nc == c))
continue;
int d = Math.abs(nr - r) + Math.abs(nc - c);
if (p[nr].charAt(nc) == 'P' && d <= 2)
return false;
else if (p[nr].charAt(nc) == 'O' && d < 2)
queue.offer(new int[] { nr, nc });
}
}
return true;
}
}
다른사람 풀이 - 1
class Solution {
public int[] solution(String[][] places) {
int[] answer = new int[places.length];
for(int t=0; t<places.length; t++) {
String[] map = places[t];
boolean flag = false;
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (map[i].charAt(j)=='P') {
if (isAroundExistPerson(i, j, map)) {
flag = true;
break;
}
}
}
if(flag){
answer[t] = 0;
break;
}
}
if(!flag){
answer[t] = 1;
}
}
return answer;
}
public static boolean isAroundExistPerson(int i, int j, String[] map){
// 상하좌우 확인
int[] mi = {0, 0, 1, -1};
int[] mj = {1, -1, 0, 0};
for (int d = 0; d < 4; d++) {
int ni = i + mi[d];
int nj = j + mj[d];
if(ni<0 || ni>=5 || nj<0 || nj>=5) continue;
if(map[ni].charAt(nj)=='P') return true;
}
// 상하좌우 맨하탄 거리 2 확인
int[] mi2 = {0, 0, 2, -2};
int[] mj2 = {2, -2, 0, 0};
for (int d = 0; d < 4; d++) {
int ni = i + mi2[d];
int nj = j + mj2[d];
if(ni<0 || ni>=5 || nj<0 || nj>=5) continue;
if(map[ni].charAt(nj)=='P') {
if(map[(i+ni)/2].charAt((j+nj)/2)!='X'){
return true;
}
}
}
// 대각선 확인
int[] mi3 = {1, 1, -1, -1};
int[] mj3 = {1, -1, 1, -1};
for (int d = 0; d < 4; d++) {
int ni = i + mi3[d];
int nj = j + mj3[d];
if(ni<0 || ni>=5 || nj<0 || nj>=5) continue;
if(map[ni].charAt(nj)=='P') {
if(!(map[i].charAt(nj)=='X' && map[ni].charAt(j)=='X')){
return true;
}
}
}
return false;
}
}
'프로그래머스 코딩테스트_도서실습' 카테고리의 다른 글
개인정보 수집 유효기간 (0) | 2024.02.03 |
---|---|
[코딩테스트_도서실습] 문자열 - 행렬의 곱셉 - Lv2 (0) | 2023.07.08 |
[코딩테스트_도서실습] 문자열 - 삼각달팽이 - Lv2 (0) | 2023.07.08 |
[코딩테스트_도서실습] 배열 - 교점에 별 만들기 - Lv2 (0) | 2023.07.08 |
[코딩테스트_도서실습] 문자열 - 이진 변환 반복하기 - Lv2 (0) | 2023.07.08 |