[プログラマ]柱と梁の取り付け(JS)

質問する

[2020 KAKAO BLIND RECRUITMENT]柱とビーム取付
[リンク]https://programmers.co.kr/learn/courses/30/lessons/60061

問題を解く

最初はもちろん2次元配列で与えられた条件に従って実現し,解決する.そんな言葉が強すぎる.また,x,y座標値も通常用いられる2次元配列と一致せず,最後に返さなければならない正解のフォーマットも理解できない.
こうして実装に時間を費やし、他の人もこのように実装して解決したのかどうかを検索していましたが、2次元配列さえ発表しない方法があるのを見て驚きました...
その解答方法の考え方はこうです.
1.ビルの現在の状態をSetに設定します.
2.作業手順に従ってインストール、削除します.
3.設置、削除のたびに、ビルの現在の状態が可能かどうかを確認します.
4.チェックして実行できない場合は、インストール、削除の前に戻ります.
ビルの現在のステータスが実行可能かどうかを確認する関数を作成すると、非常に簡単に解決されます.

柱(x,y,0)

柱は床に取り付けることができます.yの値が0の場合、有効柱(y==0)

下に柱があれば正しい柱です.現在のビルの値が(x,y-1,0)の場合、有効柱です.

柱の起点が左で、右の中に梁があれば、正柱である.下図は(x-1,y,1),(x,y,1)です.同様に、現在のビルをチェックしてください.

ステップ(x,y,1)

は、ビューカラムに取り付けられます.下に柱(x,y-1,0),(x+1,y-1,0)があればビルをチェックしてください.

両方にボーリング穴があれば取り付けることができます.(x-1,y,1)&&(x+1,y,1)両方がビル内にあることを確認します.

最初は条件を漏らしていませんでしたが、最終提出で3-9回しか正解がなかったので時間がかかりました.
問題を探す過程で配列をstringに変換して解きましたx=12y=1,a=0を見つけた場合,1210,x=1,y=21の後,a=0の間に1210を加えて解決する.,'12,1,0'はこのように修正される.

コード#コード#

function solution(n, build_frame) {
//빌딩은 add,delete,has를 이용하기 위해 set으로 설정.
   const building = new Set();
   for(let [x,y,a,b] of build_frame){
       if(b===0){
         //빌딩에는 동작(설치,삭제)인 b를 제외하고 x,y,a만 넣어준다. 
         //자바스크립트 set에서는 [1,2]===[1,2]를 false로 반환하기 때문에 set에 스트링으로 만들어 넣어준다.
         //','로 구분해주는 이유는 1<=n<=1000이기 자릿수 구분을 위해서.
           building.delete(x+','+y+','+a);
           if(isPossible(building))continue;//삭제 후에도 가능한 빌딩이면 삭제하고 continue;
           else building.add(x+','+y+','+a);//아닐시 다시 추가해서 삭제를 취소
       }else{
           building.add(x+','+y+','+a);
           if(isPossible(building))continue;//삭제와 동일
           else building.delete(x+','+y+','+a);
       }
   }
 //스트링으로 되어있는 빌딩을 return 조건에 맞추어 다시 숫자배열로 변환함.
   return [...building].map((v)=>v.split(',').map((str)=>Number(str))).sort((a,b)=>{
     //정렬 조건은 x값 우선 이후에 y값,그리고 기둥(0)이 보(1) 보다 우선 결국 모두 오름차순으로 정렬해주면된다.
       if(a[0]===b[0]&&a[1]===b[1]) return a[2]-b[2];
       if(a[0]===b[0])return a[1]-b[1];
       return a[0]-b[0];
   });
 
 //가능한 건물인지 체크하는 함수
 function isPossible(building){
   for(let xya of building){
     //스트링으로 만들어준 xya를 다시 숫자로 변환
       let [x,y,a]=xya.split(',').map(v=>Number(v));
       if(a===0){
         //올바른 기둥 조건
           if(y===0||building.has(x+','+(y-1)+','+0)||building.has((x-1)+','+y+','+1)||building.has(x+','+y+','+1))continue;
           else return false;
       }else{
         //올바른 보 조건
           if(building.has(x+','+(y-1)+','+0)||building.has((x+1)+','+(y-1)+','+0)||(building.has((x-1)+','+y+','+1)&&building.has((x+1)+','+y+','+1)))continue;
           else return false;
       }
   }
   return true;
}

}