[CodeKata] 프로그래머스 : 8.22(일), 기둥과 보 설치

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

* 실패한 풀이이다. 예제코드는 모두 맞췄으나, 실제 문제는 거의다 실패가 발생하였다.

const str = (a) => { return a === 0 ? "p" : "b" };
const cmd = (b) => { return b === 1 ? "add" : "remove" };

function solution(n, build_frame) {
  let ground = Array.from({ length: n+1 }, () => { return new Array(n+1).fill(0) });
  let answer = [];
  
  const checkCross = (x,y,dir) => {
    const dirObj = {
      n: x-1 >= 0 ? ground[x-1][y] : null,
      s: x+1 <= n ? ground[x+1][y] : null,
      e: y+1 <= n ? ground[x][y+1] : null,
      w: y-1 >= 0 ? ground[x][y-1] : null,
    }
    return dir.reduce((acc,cur) => { return dirObj[cur] === 1 ? [...acc, dirObj[cur]] : acc }, []).includes(1);
  }
  
  build_frame.forEach((build, i) => {
    let [y,x,a,b] = build;
    x = n - x, a = str(a), b = cmd(b);
    
    if (b === 'add') {
      if (a === 'p' && (x === n || ground[x][y] === 1)) {
        ground[x][y] = ground[x-1][y] = 1
      }
      if (a === 'b' && [ground[x][y], ground[x][y+1]].includes(1)) {
        ground[x][y] = ground[x][y+1] = 1
      }
    }
    
    else {
      if (a === 'p') {
        if (ground[x-2][y] === 1 || (ground[x-1][y] === 1 && ground[x-1][y-1] === 1 && ground[x-1][y-2] === 0) || (ground[x-1][y] === 1 && ground[x-1][y+1] === 1 && ground[x-1][y+2] === 0)) return;
        if (!checkCross(x-1,y,['e','w'])) ground[x-1][y] = 0
        if (!checkCross(x,y,['s','e','w'])) ground[x][y] = 0
      }
      if (a === 'b') {
        if (ground[x-1][y] === 1 || ground[x-1][y+1] === 1 
            || (ground[x][y-1] === 1 && ground[x][y-2] === 1 && ground[x][y-3] === 0) 
            || (ground[x+1][y+1] === 1 && ground[x+1][y+2] === 1 && ground[x][y+3] === 0)) return;
        if (!checkCross(x,y+1,['n','s','e','w'])) ground[x][y+1] = 0;
        if (!checkCross(x,y,['n','s','e','w'])) ground[x][y] = 0;
      }
    }
  })

  for (let y = 0 ; y <= n ; y++) {
    for (let x = n ; x >= 0 ; x--) {
      if (ground[x][y] === 1) {
        if (ground[x-1][y] === 1) answer.push([y,n-x,0])
        if (ground[x][y+1] === 1) answer.push([y,n-x,1])
      }
    }
  }
  return answer;
}

한 좌표에 기둥과 보가 중첩되는 경우가 있어, 기둥 혹은 보가 설치된 앞뒤좌표를 1, 빈 좌표는 0으로 누적하는 ground를 만들었다.

짓는 경우(add), 기둥은 아래쪽이 1, 보는 왼쪽이나 오른쪽 둘 중 하나가 1인 경우에 가능하다.

지우는 경우(remove), 기둥은 위가 기둥이거나 보인 경우 불가하여 return 처리한다. 보는 좌우 위에 기둥이 있거나 보가 떠있는 경우 return 처리한다.

만약 삭제가 가능하다면, checkCross() 함수를 통해 필요한 동서남북을 확인하여 삭제하면 된다.

기둥/보가 아닌 0과 1로 설치여부를 관리하다보니, 예외인 경우도 많고 이를 매칸마다 0과 1인지 판별해야 하므로 매우 복잡해졌다.

 

🖇 리뷰

function solution(n, build_frame) {
    const answer = [];
    const gi=Array.from(Array(n+2),()=> Array(n+2).fill(0));
    const bo=Array.from(Array(n+2),()=> Array(n+2).fill(0));
    
    /**
     	해당 좌표(y,x)에 기둥 혹은 보를 설치할 수 있는지 판단한다.
    **/
    function check(y,x,type){
        if(type===0){
            if(y===n) return true;   
            if(gi[y+1][x]) return true;
            if(bo[y][x] || (x>0 && bo[y][x-1])) return true;
        }else{
            if(gi[y+1][x] || (x<n && gi[y+1][x+1])) return true;
            if(x>0 && bo[y][x-1] && bo[y][x+1]) return true;
        }
        return false;
    }
    
    /**
    	모든 기둥과 보가 설치조건을 만족하는지 판단한다.
    **/
    function enableDelete(){
        for(let i=1;i<=n;i++){
            for(let j=0;j<=n;j++){
                if(!gi[i][j]) continue;
                if(!check(i,j,0)) return false;
            }
        }
        for(let i=0;i<n;i++){
            for(let j=0;j<n;j++){
                if(!bo[i][j]) continue;
                if(!check(i,j,1)) return false;
            }
        }
        return true;
    }
    /**
    	기둥과 보 설치, 삭제
    **/
    for(let i=0;i<build_frame.length;i++){
        const y=n-build_frame[i][1];
        const x=build_frame[i][0];
        const type=build_frame[i][2];
        const behave=build_frame[i][3];
        
        if(behave===1){
            if(type===0 && check(y,x,0)) gi[y][x]=1;
            else if(type===1 && check(y,x,1)) bo[y][x]=1;
        }
        else{
            if(type===0){
                gi[y][x]=0;
                if(!enableDelete()) gi[y][x]=1;
            }            
            else{
                bo[y][x]=0;
                if(!enableDelete()) bo[y][x]=1;
            }
        }
    }
    
    function makeAnswer(){
        for(let j=0;j<=n;j++){
             for(let i=n;i>=0;i--){
                if(gi[i][j]) answer.push([j,n-i,0]);
                if(bo[i][j]) answer.push([j,n-i,1]);
            }
        }
        
    }
    makeAnswer();
    return answer;
}

* 출처 : https://gwang920.github.io/algorithm/progreammers-2-60061/ 

• 우선, 기둥 설치여부(gi)와 보 설치여부(bo)를 각각의 2차원 배열로 관리했다. 해당 좌표에 설치가 가능하다면 1을, 아니면 0을 누적.
• 또한, 내 문제와 마찬가지로 JS 2차원 배열 좌표형태를 이용하기 위해, x는 그대로, y는 n-y를 통해 뒤집어주었다.
• check() 함수는 해당위치에 설치가 가능한지 판별하는 함수이다. 기둥은 바닥인 경우 혹은 아래에 기둥이나 보가 있는 경우, 보는 양쪽 아래에 기둥 혹은 보가 있는 경우 true를, 이외는 불가하므로 false를 반환한다.
• enableDelete() 는 삭제후 상태가 정상적인지 검사하는 함수이다. 이는 먼저 삭제를 진행한 뒤, 전체검사 후 문제가 있는 경우 이전 상태로 복귀시키는 방법을 사용했다. 기둥과 보가 설치된 좌표에서, 해당 기둥과 보가 현재 적합한지 검사하는 것이다.
• 다시 풀이부분으로 내려오면, build_frame 각 인자를 x, y(n-y), type(기둥/보), behave(설치/삭제) 변수에 각각 저장했다.
• behave 1은 설치이므로, 각 type에서 check()를 진행하여 이상없으면 gi 혹은 bo에 해당좌표에 1을 넣어 설치처리한다.
• 이외엔 삭제이므로, 기둥/보를 0으로 삭제처리한 뒤 enableDelete() 검사를 통해 이상이 있는 경우 이를 다시 1로 재반영한다. (만약 기둥만 삭제했더라도, 보가 공중에 떠잇는 등 문제가 생길 수 있으므로 enableDelete()는 기둥/보 모든 경우를 검사한다.)
• makeAnswer() 함수는 최종 gi, bo 를 순회하면서 answer에 정답을 누적해주는 함수이다. 정리된 answer를 최종 반환한다.

 

우선, 기둥/보 시작, 끝점을 1로 누적해가던 내 방법에 비해, 기둥/보 설치가능 좌표만 누적하는 위 방법이 훨씬 깔끔했다.

또한, gi와 bo를 각각 따로 관리하면서, 내가 이 둘을 한 좌표에 String 혹은 Array로 저장하려했던 고민에 대한 해답을 제시했다.

 

또한, check()와 enableDelete() 설치/삭제 가능여부를 각각의 함수로 구성한 부분도 인상깊다.

특히, 삭제를 우선 진행한 다음 전체검사를 하여 부적절한경우 이를 다시 돌린다는 방법이 매우 직관적이었다.

(다른 풀이에서는 전체검사가 아니라, 3*3 범위만 봐도 된다고 함)