첫 시도는 단순 구현이었습니다.
첫번째 케이스는 크게 어렵지 않게 풀 수 있었으며 삭제 로직을 구현함에 있어서 어려움이 있었습니다.
삭제에 대한 예외처리를 구현할때 시도한 방법은,
지금 내가 삭제 할 수 있는 기둥인가에 대한 확인이었습니다.
일반적인 테스트의 경우 가능하지만 완전 한가운데의 기둥을 제거 할때, 어디까지 떨어져 있는 기둥까지 찾아야 하는가에 대한 어려움을 구현하지 못하였습니다.
function solution(n, build_frame) {
var answer = [];
const building = new Array(n+1).fill(0).map(()=> new Array(n+1).fill(0).map(()=>{ return {
"bo" : false,
"gidoong" : false,
}
}))
for(let i=0; i< build_frame.length; i++){
const [curX, curY, type, isBuild] = build_frame[i]
// type은 0이면 기둥, 1이면 보를 설치
// isBuild 는 0이면 삭제, 1이면 설치
// isBuild에 따른 분류
// 설치 - 설치 할때는 중복되어 제공 되지 않는다.
if(isBuild === 1){
if(type === 0){ // 기둥 설치
// 좌표에 기둥을 두기 위해서는 바닥위, 혹은 보의 위에 있는지, 기둥위에 있는지 확인합니다.
if(curY === 0){ // 바닥위
building[curX][curY].gidoong = true;
continue;
}else if( building[curX][curY-1].gidoong){ // 기둥 위에 있는지
building[curX][curY].gidoong = true;
continue;
}else if(building[curX-1][curY].bo || building[curX][curY].bo ){ // 보 위에 있는지
building[curX][curY].gidoong = true;
continue;
}
}else if(type ===1){ // 보 설치
// 보를 설치하기 위해서는 바로 y로 바로 아래 좌표에 기둥이 있는지, 혹은 x로 양쪽 떨어진 부분에 보가 있는지 확인
if(building[curX][curY-1].gidoong){// 기둥 위에 있는지
building[curX][curY].bo = true;
continue;
}else if(building[curX+1][curY-1].gidoong){
building[curX][curY].bo = true;
continue;
}else if(building[curX-1][curY].bo && building[curX+1][curY].bo){//양쪽에 보가 있는지 확인
building[curX][curY].bo = true;
continue;
}
}
}
// 삭제
else{
if(type === 0){ // 기둥 삭제
//만약 없다면 바로 넘기기
if(!building[curX][curY].gidoong){
continue;
}
// 기둥을 삭제할 수 있는 경우만 찾아보자
// 기둥의 상단에 아무것도 없을것, -> 제거 가능
if(!building[curX][curY+1].bo && !building[curX][curY+1].gidoong){
building[curX][curY].gidoong = false;
continue;
}else if(building[curX][curY+1].bo && building[curX+1][curY].gidoong){
building[curX][curY].gidoong = false;
continue;
}else if(building[curX-1][curY+1].bo && building[curX+1][curY].gidoong){
}
// 기둥의 상단에 보만 있는경우 -> 양쪽에 보가 있거나, 양쪽의 보가 기둥에 걸쳐 있어야함
}else if(type ===1){ // 보 삭제
// 보를 삭제함으로 양쪽의 보가 무너지지는 않는지 확인한다. 양쪽에 보가 있다면 양쪽 아래에 기둥이 있어야 한다.
}
}
}
for(let x =0; x < n+1; x++){
for(let y=0; y < n+1; y++){
if(building[x][y].gidoong || building[x][y].bo){
if(building[x][y].gidoong){
answer.push([x,y,0])
}
if(building[x][y].bo){
answer.push([x,y,1])
}
}
}
}
return answer;
}
// 설치할때는 어떻게 확인할까. result에 다 넣고 찾기?
첫번째 케이스는 확인하였지만, 두번째 케이스부터 문제가 생겼습니다.
longroadhome님의 풀이를 보니 아주 깔끔한 코드를 확인할 수 있었습니다.
모든 위치에서 설치가 가능했던 것인지 확인하는 것이 중요하다.
이를 구현하기 위해서 longroadhome 님은 함수를 정확히 용도에 맞게 나누어 구현하셨다.
function solution (n, build_frame) {
const answer = [];
for(const frame of build_frame) {
const [x, y, fr, isInstall] = frame;
if(isInstall) buildFrame(answer, x, y, fr); // 설치한다면,
else destroyFrame(answer, x, y, fr); // 제거 한다면?
}
return answer.sort((a, b) => a[0] === b[0] ? a[1] === b[1] ? a[2] - b[2] : a[1] - b[1] : a[0] - b[0]);
}
const buildFrame = (ans, x, y, frame) => {
if(frame) {
if(checkPlate(ans, x, y)) ans.push([x, y, frame]); // 판을 확인하여 설치
}
else {
if(checkPillar(ans, x, y)) ans.push([x, y, frame]);// 기둥을 설치한다
}
}
const destroyFrame = (ans, x, y, frame) => {
const copy = [...ans];
const idx = ans.findIndex(([a, b, fr]) => a===x && b===y && fr===frame);
copy.splice(idx, 1);
for(const frs of copy) { // 제거 할 위치를 하나 제거 한후 여기서 모든 원소에 대해서 check를 수행한다. 이때 순서는 신경쓰지 않는다.
const [xpos, ypos, fr] = frs;
if(fr) {
if(!checkPlate(copy, xpos, ypos)) return;
}
else {
if(!checkPillar(copy, xpos, ypos)) return;
}
}
ans.splice(idx, 1); // 만약 문제가 있다면 그 위치를 제거
}
const checkPillar = (ans, x, y) => { // 판을 설치하기 위한 조건
if(y === 0) return true;
else if(ans.find(([a, b, fr]) => a===x && b===y-1 && fr === 0)) return true;
else if(ans.find(([a, b, fr]) => a===x && b===y && fr===1)) return true;
else if(ans.find(([a, b, fr]) => a===x-1 && b===y && fr===1)) return true;
return false;
}
const checkPlate = (ans, x, y) => {// 기둥을 설치 하기 위한 조건
if(ans.find(([a, b, fr]) => a===x && b===y-1 && fr===0)) return true;
else if(ans.find(([a, b, fr]) => a===x+1 && b===y-1 && fr===0)) return true;
else if(ans.find(([a, b, fr]) => a===x+1 && b===y && fr===1) &&
ans.find(([a, b, fr]) => a===x-1 && b===y && fr===1)) return true;
return false;
}