프로그래머스: 기둥과 보 설치 (빡센 구현)

문제 출처 

https://school.programmers.co.kr/learn/courses/30/lessons/60061

프로그래머스

 

문제 풀이 힌트 

이 코드는 기둥과 보의 설치 및 삭제 명령을 처리하여 최종 구조물을 결정한다 ! 

 

1) 각 구조물의 상태를 문자열 키로 변환하여 Set에 저장하고, 설치 및 삭제 명령에 따라 유효성을 확인

2) 설치 명령은 조건을 만족할 때만 구조물을 추가하고,

3) 삭제 명령은 임시로 구조물을 제거한 후 모든 구조물이 유효한지 확인한다. 

4) 최종적으로 구조물 리스트를 좌표와 구조물 종류에 따라 정렬하여 반환합니다.

 

이 방법은 Set을 사용하여 효율적인 검색과 업데이트를 보장한다. 

정답 풀이 코드 

function solution(n, build_frame) {
    const answer = new Set();
    
    // 각 명령어를 순차적으로 처리
    for (const frame of build_frame) {
        const [x, y, fr, isInstall] = frame;
        const key = `${x},${y},${fr}`; // 구조물의 위치와 종류를 문자열로 변환하여 키 생성
        
        if (isInstall) {
            // 설치 명령
            if (buildFrame(answer, x, y, fr)) {
                answer.add(key); // 설치 가능하면 추가
            }
        } else {
            // 삭제 명령
            answer.delete(key); // 임시로 삭제
            if (!isValid(answer)) {
                answer.add(key); // 유효하지 않으면 다시 추가
            }
        }
    }
    
    // 결과를 배열로 변환하여 정렬 후 반환
    return [...answer]
        .map(str => str.split(',').map(Number)) // 문자열을 숫자로 변환
        .sort((a, b) => 
            a[0] === b[0] ? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0]
        );
}

// 현재 구조물이 유효한지 확인하는 함수
const isValid = (ans) => {
    for (const item of ans) {
        const [x, y, fr] = item.split(',').map(Number);
        if (fr === 0) {
            if (!checkPillar(ans, x, y)) return false; // 기둥이 유효한지 확인
        } else {
            if (!checkPlate(ans, x, y)) return false; // 보가 유효한지 확인
        }
    }
    return true;
}

// 기둥이 설치될 수 있는지 확인하는 함수
const checkPillar = (ans, x, y) => {
    return y === 0 || // 바닥에 설치되는 경우
        ans.has(`${x},${y-1},0`) || // 아래에 기둥이 있는 경우
        ans.has(`${x},${y},1`) || // 보의 오른쪽 끝에 있는 경우
        ans.has(`${x-1},${y},1`); // 보의 왼쪽 끝에 있는 경우
}

// 보가 설치될 수 있는지 확인하는 함수
const checkPlate = (ans, x, y) => {
    return ans.has(`${x},${y-1},0`) || // 왼쪽 아래에 기둥이 있는 경우
        ans.has(`${x+1},${y-1},0`) || // 오른쪽 아래에 기둥이 있는 경우
        (ans.has(`${x-1},${y},1`) && ans.has(`${x+1},${y},1`)); // 양쪽에 보가 있는 경우
}

// 구조물을 설치하는 함수
const buildFrame = (ans, x, y, frame) => {
    if (frame === 1) { // 보인 경우
        return checkPlate(ans, x, y);
    } else { // 기둥인 경우
        return checkPillar(ans, x, y);
    }
}

Only 정답 코드 

function solution(n, build_frame) {
    const answer = new Set();
    
    for (const frame of build_frame) {
        const [x, y, fr, isInstall] = frame;
        const key = `${x},${y},${fr}`;
        
        if (isInstall) {
            if (buildFrame(answer, x, y, fr)) {
                answer.add(key);
            }
        } else {
            answer.delete(key);
            if (!isValid(answer)) {
                answer.add(key);
            }
        }
    }
    
    return [...answer]
        .map(str => str.split(',').map(Number))
        .sort((a, b) => a[0] === b[0] ? (a[1] === b[1] ? a[2] - b[2] : a[1] - b[1]) : a[0] - b[0]);
}

const isValid = (ans) => {
    for (const item of ans) {
        const [x, y, fr] = item.split(',').map(Number);
        if (fr === 0) {
            if (!checkPillar(ans, x, y)) return false;
        } else {
            if (!checkPlate(ans, x, y)) return false;
        }
    }
    return true;
}

const checkPillar = (ans, x, y) => {
    return y === 0 || ans.has(`${x},${y-1},0`) || ans.has(`${x},${y},1`) || ans.has(`${x-1},${y},1`);
}

const checkPlate = (ans, x, y) => {
    return ans.has(`${x},${y-1},0`) || ans.has(`${x+1},${y-1},0`) || (ans.has(`${x-1},${y},1`) && ans.has(`${x+1},${y},1`));
}

const buildFrame = (ans, x, y, frame) => {
    if (frame === 1) {
        return checkPlate(ans, x, y);
    } else {
        return checkPillar(ans, x, y);
    }
}

틀린 풀이 코드

function solution(n, build_frame) {
    let graph = Array.from({length: n}).map(() => new Array(n).fill(-1)); 
    for(let i=0; i<build_frame.length; i++){
      const [x,y,a,b] = build_frame[i]; 
      if(b === 1){ //설치 
          if(a === 0){ //기둥
              //설치 가능할 때 
              if(y === 0 || graph[x][y] === 1 || graph[x-1][y] === 1 || graph[x][y-1] === 0){
                  graph[x][y] = 0 
              }
          }else{//보 
              if(graph[x][y-1] === 0 || graph[x+1][y-1] || (graph[x-1][y] && graph[x+1][y])){
                  graph[x][y] = 1
              }
          }
      }else{ //삭제 
          if(a === 0){//기둥
              if(graph[x-1][y+1] !== 1 || graph[x][y+1] !== 1 || graph[x][y+1] !== 0){
                  graph[x][y] = -1
              }
          }else{//보 
              if(graph[x+1][y] !== 0 || graph[x][y] !== 0 || !(graph[x+1][y] === 1 && graph[x+2][y] === 1) || !(graph[x-1][y] === 1 && graph[x-2][y] === 1)){
                 graph[x][y] = -1 
              }
          }
      }
    }
    let result = []; 
    for(let i=0; i<n; i++){
        for(let j=0; j<n; j++){
            if(graph[i][j] !== -1){
                result.push([x,y,graph[x][y]])
            }
        }
    }
    return result.sort((a,b) => a[2] - b[2])
}
//죠르디 주택건축사업 
//기둥과 보 , 벽면 구조물 세우는 로봇 개발 계획 
//[가로, 세로]
//설치하고, 삭제하는 작업 2차원 배열 
//return 구조물 상태 

//기둥: 바닥 위, 보의 한쪽 끝 부분 위에, 다른 기둥 위 
//보: 한쪽 끝 부분이 기둥 위, 양쪽 끝 부분이 다른 보와 동시 연결 
//x: 가로, y: 세로 
//a는 기둥(0) 혹은 보(1) 
//b는 삭제(0) or 설치(1)
//바닥에 보 설치 x 
//보는 오른쪽 설치, 기둥은 위쪽 설치 
//return x좌표 기준 오름차순 정렬, y좌표 오름차순 정렬 , 완전 똑같으면 기둥이 먼저 

//실시간으로 그래프를 그리면서 or?/ and bfs로 주변 살피는 거 
//조건에 맞는다면 
//기둥과 보를 설치 및 삭제 
//return 마지막 sort 정렬 

//기둥을 세울 수 있는 조건 
//-바닥일 때: [ ,0]
//-보의 한쪽 끝 부분 위 : 보가[1,1]일 때 =>[1,1] [2,1] 가능 
//-다른 기둥 위: 기둥: 기둥 [5,0]일 때 => [5,1]가능 
//보를 설치할 수 있는 조건 
//-한쪽 끝 부분이 기둥 위: 기둥이[1,0]일 때 => [1,1] [0,1]가능 
//-양쪽 끝 부분이 다른 보와 동시 연결: 보가 [2,2]와[4,2]일 때 => [3,2]가능
//기둥을 삭제할 수 있는 조건 
//-기둥이 (5,1)이였을 때 => (4,2)에 보가 없어야 함. 왼쪽 보 
//-기둥이 (0,0)이였을 때 => (0,1)에 보가 없어야 함, 오른쪽 보 
//-기둥이 (5,0)이엿을 때 => (5,1)에 기둥이 없어야 함. 위에 기둥이 있나 
//보를 삭제할 수 있는 조건 
//-보가 (1,1)이였을 때 => (2,1)에 기둥이 없어야 함. 오른쪽 기둥 
//-보가 (0,1)이였을 때 => (0,1)에 기둥이 없어야 함. 왼쪽 기둥 
//-보가 (2,2)이였을 때 => (3,2)에 보가 (4,2)에 보가 없어야 함. 오른쪽 보 
//-보가 (4,2)이였을 때 => (2,2)에 보가 (3,2)에 보가 없어야 함. 왼쪽 보