문제 출처
나의 풀이
1차시도 (47.5/100)
function solution(places) {
let answer = [];
const cascade = [[1,1], [-1,1], [-1,-1], [1,-1]]
const vertical = [[-2,0], [-1,0], [1,0], [2,0]]
const horizon = [[0,-2], [0,-1], [0,1], [0,2]]
const distancing = [cascade, vertical, horizon];
places.map(place => {
let flag=true;
// console.log(place);
for(let y=0; y<place.length; y++) {
for(let x=0; x<place[0].length; x++) {
// console.log(place[y][x]);
if(place[y][x] === 'P') {
// console.log(y, x);
for(let l=0; l<distancing.length; l++) {
for(let k=0; k<distancing[l].length; k++) {
let dy = y + distancing[l][k][0];
let dx = x + distancing[l][k][1];
if(dy<0||dx<0||dy>place.length-1||dx>place[0].length-1) continue;
// console.log(l, dy,dx);
if(place[dy][dx] === 'P') {
// console.log(l, dy, dx, Math.abs(distancing[l][k][1]));
flag=false;
if(l===0) {
if(place[y][dx] === 'X' && place[dy][x] === 'X') {
flag=true;
break;
}
}
else if(l===1 && Math.abs(distancing[l][k][0])===2) {
dy -= (distancing[l][k][0]/2);
if(place[dy][dx] === 'X') {
flag=true;
break;
}
}
else if(l===2 && Math.abs(distancing[l][k][1])===2) {
dx -= (distancing[l][k][1]/2);
if(place[dy][dx] === 'X') {
flag=true;
break;
}
}
}
// console.log(flag);
}
}
}
}
}
if(flag) answer.push(1)
else answer.push(0);
})
return answer;
}
console.log(
solution([
["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]2차시도 (통과)
flag 판단 부분만 변경해서 통과했다. (false => true 때 break가 아니라 true => false일 때 break 흐름으로 변경. 전자로 할 경우, 앞에서 false가 나와도 뒤에서 true로 덮이는 경우가 발생하기 때문)
방향 이동에 따른 각 경우에 대해서 조건을 만족하는지 판단하면 된다.맨해튼 거리가 2보다 큰 경우는 거리두기 조건을 만족하므로 고려하지 않아도 된다. 맨해튼 거리가 2 이하인 경우에 대해서만 판단하면 되는데,
- cascade : y와 x를 1씩 모두 움직이는 경우
- vertical : y만 움직이는 경우 (2까지 움직일 수 있다)
- horizon : x만 움직이는 경우 (2까지 움직일 수 있다)
place[y][x]가 P인 경우에 대해서 위 경우의 수에 맞게 dy,dx 값을 지정해서 판단한다.
- cascade인 경우(l===0)
: place[y][dx]와 place[dy][x] 모두가 'X'여야 하며 아니라면 false이다. - vertical인 경우(l===1)
: 중간 자리가 'X'여야 하므로 dy값에 (distancing[l][k][0]/2)를 빼서 판단해준다. 'X'가 아니면 false이다. - horizon인 경우(l===2)
: 마찬가지로 중간 자리가 'X'여야 하므로 dx값에 (distancing[l][k][1]/2)를 빼서 판단해준다. 'X'가 아니면 false이다. - 위 세 경우 공통
: 이동거리가 1이라면(Math.abs(distancing[l][k][0])===1) 무조건 false이다.
function solution(places) {
let answer = [];
const cascade = [[1,1], [-1,1], [-1,-1], [1,-1]]
const vertical = [[-2,0], [-1,0], [1,0], [2,0]]
const horizon = [[0,-2], [0,-1], [0,1], [0,2]]
const distancing = [cascade, vertical, horizon];
places.map(place => {
let flag=true;
// console.log(place);
for(let y=0; y<place.length; y++) {
for(let x=0; x<place[0].length; x++) {
// console.log(place[y][x]);
if(place[y][x] === 'P') {
// console.log('P', y, x);
for(let l=0; l<distancing.length; l++) {
for(let k=0; k<distancing[l].length; k++) {
let dy = y + distancing[l][k][0];
let dx = x + distancing[l][k][1];
if(dy<0||dx<0||dy>place.length-1||dx>place[0].length-1) continue;
// console.log(l, dy, dx);
if(place[dy][dx] === 'P') {
// console.log(l, dy, dx, Math.abs(distancing[l][k][1]));
if(l===0) {
if(place[y][dx] !== 'X' || place[dy][x] !== 'X') {
flag=false;
break;
}
}
else if(l===1) {
if(Math.abs(distancing[l][k][0])===2) {
dy -= (distancing[l][k][0]/2);
if(place[dy][dx] !== 'X') {
flag=false;
break;
}
}
else if(Math.abs(distancing[l][k][0])===1) {
flag=false;
break;
}
}
else if(l===2) {
if(Math.abs(distancing[l][k][1])===2) {
dx -= (distancing[l][k][1]/2);
if(place[dy][dx] !== 'X') {
flag=false;
break;
}
}
else if(Math.abs(distancing[l][k][1])===1) {
flag=false;
break;
}
}
}
// console.log(flag);
}
}
}
}
}
if(flag) answer.push(1)
else answer.push(0);
})
return answer;
}
console.log(
solution([ // 반례 추가
["OPOPO", "OXXOX", "OPXPX", "OOXOX", "POXXP"],
["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"],
])
); // [0, 1, 0, 1, 1, 1]맨해튼 거리
가운데 초록색이 유클리드 거리이다.
하지만 좌표가 아니라 도시라면, 초록색처럼 가로질러서 다닐 수 없다. 그래서 빨간색, 파란색, 노란색처럼 다녀야 하는데, 보기와 달리 세 경우 모두 거리가 같다.
그래서 도시에서는 높이+너비가 최단거리라는 것.
좌측하단의 좌표가 (y1,x1), 우측상단의 좌표가 (y2,x2)라면
⇒ (평면 위에서) Math.abs(y2-y1) + Math.abs(x2-x1)
다른 풀이
방향 판단 문제의 경우,
각 노드에서 (다음 노드로 이동하기 전에) 방향 판단이 우선되어야 하므로 DFS보다 BFS가 적절하다.
'X' 판단하는 게 핵심인데, 'X'만 판단하는 거라면 4방향(위,아래,좌,우)만 돌아도 된다.
function solution(places) {
const move = [[0, -1],[0, 1],[1, 0],[-1, 0]];
const SIZE = 5;
const isValid = (x, y) => x >= 0 && y >= 0 && x < SIZE && y < SIZE;
const isAvailableSeat = (x, y, checked) =>
isValid(x, y) && checked[x][y] === 0;
// bfs
const checkAround = (start, room, checked) => {
let queue = [start];
while (queue.length > 0) {
const [x, y, n] = queue.shift();
if (n !== 0 && room[x][y] === "P") return false;
move.forEach(([mx, my]) => {
const _x = x + mx;
const _y = y + my;
if (isAvailableSeat(_x, _y, checked) && room[_x][_y] != "X") {
if (n < 2) {
checked[_x][_y] = 1;
queue.push([_x, _y, n + 1]);
}
}
});
}
return true;
};
const checkDistancing = (room) => {
let checked = Array.from({ length: SIZE }, () => Array(SIZE).fill(0));
for (let i = 0; i < SIZE; i++) {
for (let j = 0; j < SIZE; j++) {
if (room[i][j] !== "P") continue;
checked[i][j] = 1;
if (!checkAround([i, j, 0], room, checked)) return 0;
}
}
return 1;
};
return places.map(checkDistancing);
}다른 풀이
출처 : [Programers][Javascript] 거리두기 확인하기 (2021 카카오 인턴쉽)
P일 때 : 상,하,좌,우에 P가 존재하면 거리두기 실패
O일 때 : 상,하,좌,우에 P가 2개 이상 있으면 거리두기 실패
function solution(places)
{
var answer = places.map(place => {
// 결과가 true 이면 거리두기가 지켜지지 않음
return place.some((row, rowIndex) => {
// true 이면 거리두기가 지켜지지 않음, 바로 종료
return row.split('').some((column, index, arr) => {
// 파티션이 있으면 거리두기 지킴
if (column == 'X') return false;
// 상하좌우에 P가 몇개인지 조회
const userCount = [
arr[index - 1] || null, // 좌
arr[index + 1] || null, // 우
(place[rowIndex - 1] || '').charAt(index), // 상
(place[rowIndex + 1] || '').charAt(index), // 하
].filter(v => v == 'P').length;
if((column == 'P' && userCount > 0) || // P기준 상하좌우에 P가 있는지
(column == 'O' && userCount >= 2)) { // O기준 상하좌우에 P가 2개 이상인지
return true;
}
return false;
}, '');
}) ? 0 : 1;
});
return answer;
}Array.prototype.some() : 배열 안 어떤 요소라도 주어진 판별 함수를 통과하는지 true/false
const array = [1, 2, 3, 4, 5];
// checks whether an element is even
const even = (element) => element % 2 === 0;
console.log(array.some(even));
// expected output: trueArray.prototype.every() : 배열 안 모든 요소가 주어진 판별 함수를 통과하는지 true/false
const isBelowThreshold = (currentValue) => currentValue < 40;
const array1 = [1, 30, 39, 29, 10, 13];
console.log(array1.every(isBelowThreshold));
// expected output: trueArray.prototype.find() : 주어진 판별 함수를 만족하는 첫번째 요소의 값을 반환하고, 없다면 undefined 반환
(값이 아니라 인덱스를 반환받으려면, Array.prototype.findIndex())
const array1 = [5, 12, 8, 130, 44];
const found = array1.find(element => element > 10);
console.log(found);
// expected output: 12참고
맨해튼 거리
[프로그래머스] 거리두기 확인하기 (2021 카카오 인턴십) / JavaScript
[Programers][Javascript] 거리두기 확인하기 (2021 카카오 인턴쉽)
https://medium.com/@wooleejaan