HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
👻
개발 기록/
코딩테스트 스터디
코딩테스트 스터디/
기둥과 보 설치

기둥과 보 설치

문제

notion image
notion image
notion image
notion image
 

풀이

현석
재영
💡
와따시… 빡구현 중 오열하고 있읍니다 🥰
 
결과: 하드코딩 후 30%만 맞춤…
뭔가 유효한지를 판단하는 메서드를 보와 기둥 각각 만들어서 계산하는 게 마음 편할 거 같아서 저장!

결과

약 8시간만에 해결! 내 시간…😭
배운 점: private class field을 이번에 처음 알게되어 써보았습니다!
클래스를 잘 써보지 않았는데, 코테를 하면서 객체지향형 프로그래밍을 조금씩 익혀보려 합니다 😊
Link
https://school.programmers.co.kr/learn/courses/30/lessons/60061
Deadline
Sep 18, 2022
Status
Archived
Type
구현
// 실패!
class Builder{
    constructor(size) {
        this._size = size
        this.createWorkSpace(size)
    }   
    
    get workSpace() {
        return this._workSpace
    }

    createWorkSpace(size) {
        this._workSpace = new Array(size)
            .fill(null)
            .map(row => new Array(size).fill(null).map(pos => new Array(2).fill(false)))
    }
    
    validateFloor([x, y]) { 
        return (y - 1 >= 0 && this._workSpace[x][y - 1][0]) 
            || (x + 1 <= this._size && y -1 >= 0  && this._workSpace[x + 1][y - 1][0])
            || (x- 1 >= 0 && this._workSpace[x - 1][y][1] && x + 1 <= this._size && this._workSpace[x + 1][y][1])
    }
    
    validatePillar([x, y]) {
        return y === 0 
            ||  (y - 1 >= 0 && this._workSpace[x][y - 1][0] )
            ||  (x - 1 >= 0 && this._workSpace[x - 1][y][1])
    }
    
    validate(type, [x, y]) {
        if (x < 0 || y < 0|| x > this._size || y > this._size) return false
        if (x === this._size && type === 1) return false
        
        if (type === 1) return this.validateFloor([x,y])
        else if (type === 0) return this.validatePillar([x,y])
    }
    
    buildFloor(position) {
        const [x, y] = position
        this._workSpace[x][y][1] = true
    }
    
    
    buildPillar(position) {
        const [x, y] = position
        this._workSpace[x][y][0] = true
    }    
    
    build(type, position) {
        const valid = this.validate(type, position)
        if (!valid) return
        
        if (type === 1) {
            this.buildFloor(position)
        } else if (type === 0) {
            this.buildPillar(position)
        }
    }
    
    destroy(type, position) {
        const [x, y] = position
        if (x < 0 || y < 0|| x > this._size || y > this._size) return false
        if (x === this._size && type === 1) return false
        
        
        if (this.testImpact(type, position)) return
        console.log(position)
        this._workSpace[x][y][type] = false
    
    }
    
    testImpact(type, position) {
        const [x,y] = position
        this._workSpace[x][y][type] = false
        
        const anothorType = 1 - type
        
        if (this._workSpace[x][y][anothorType] && !this.validate(anothorType, position)) {
            this._workSpace[x][y][type] = true
            console.log(position, type)
            return true
        }
        
        
        const dx = [1, -1, 0, 0]
        const dy = [0, 0, -1, 1]
        
        const check = ([x, y]) => {
            let result = false
            loop:
            for (let i=0; i< 4; i++) {
                const nx = dx[i] + x
                const ny = dy[i] + y
                if (nx < 0 || ny < 0 || nx > this._size || ny > this._size) continue
                
                for (let type = 0; type < 2; type++) {
                    if (!this._workSpace[nx][ny][type]) continue
                    if (!this.validate(type, [nx, ny])) {
                       result = true
                       break loop
                    }
                }
                   
            }
            
            this._workSpace[x][y][type] = true
            return result
        }
        return check(position)
    }
    
    status() {
        const result = []
        
        for (let i = 0; i < this._size; i++) {
            for (let j = 0; j < this._size; j++) {
                for(let k = 0; k < 2; k++) {
                    if (!this._workSpace[i][j][k]) continue
                    result.push([i, j, k])
                }
            }
        }
        
        return result
    }
    
}

function solution(n, build_frame) {
    const size = n + 1
    const structureType = ['pillar', 'floor']
    
    
    const builder = new Builder(size)
    build_frame.forEach(([x, y, type, method], index) => {
        
        if (method === 1) {
            builder.build(type, [x, y])
        } else if (method === 0) {
            builder.destroy(type, [x,y])
        }
    })
   
    return builder.status().sort((a,b) => a[0] - b[0] || a[1] - b [1] || a[2] - b[2])
}
class BuildMap {
  #PILLAR_CODE = 0;
  #FLOOR_CODE = 1;
  #COMMAND_ADD_CODE = 1;
  #COMMAND_DELETE_CODE = 0;

  #BuildTypes = Object.freeze({
    [this.#PILLAR_CODE]: '기둥',
    [this.#FLOOR_CODE]: '보',
  });
  #CommandTypes = Object.freeze({
    [this.#COMMAND_DELETE_CODE]: '삭제',
    [this.#COMMAND_ADD_CODE]: '추가',
  });

  constructor(n) {
    this.mapSize = n + 1;
    this.arr = Array.from(
      { length: this.mapSize },
      () => Array.from({ length: this.mapSize }, () => [false, false]) // pillar, floor(now -> right)
    );
  }

  checkBuild(x, y, buildType, commandType) {
    const commands = {
      [this.#CommandTypes[this.#COMMAND_DELETE_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]:
          this.checkDeletePillarPossible.bind(this),
        [this.#BuildTypes[this.#FLOOR_CODE]]:
          this.checkDeleteFloorPossible.bind(this),
      },
      [this.#CommandTypes[this.#COMMAND_ADD_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]:
          this.checkAddPillarPossible.bind(this),
        [this.#BuildTypes[this.#FLOOR_CODE]]:
          this.checkAddFloorPossible.bind(this),
      },
    };

    return commands[commandType][buildType](x, y);
  }

  checkAddPillarPossible(x, y) {
    if (this.arr[x][y][0]) return false;

    const isPillarBelowStand = !y || this.arr[x][y - 1][0];
    const isFloorStand = x > 0 && (this.arr[x][y][1] || this.arr[x - 1][y][1]);

    return !y || isPillarBelowStand || isFloorStand;
  }

  checkAddFloorPossible(x, y) {
    if (this.arr[x][y][1]) return false;

    const isPillarStand =
      !y ||
      this.arr[x][y - 1][0] ||
      (x < this.mapSize - 1 && this.arr[x + 1][y - 1][0]);

    const isFloorBothSide =
      x < this.mapSize - 1 &&
      x > 0 &&
      this.arr[x - 1][y][1] &&
      this.arr[x + 1][y][1];

    return isPillarStand || isFloorBothSide;
  }

  delete(x, y, buildCode) {
    this.arr[x][y][buildCode] = false;
  }

  backupBeforeDelete(x, y, buildCode) {
    this.arr[x][y][buildCode] = true;
  }

  simulateDelete(x, y, buildCode) {
    this.delete(x, y, buildCode);

    if (buildCode) {
      // floor
      const isPillarStandPossible =
        !this.arr[x][y][0] ||
        (y > 0 && this.arr[x][y - 1][0]) || // 바로 밑 기둥
        (x > 0 && this.arr[x - 1][y][1]); // 왼쪽 보

      const isRightPillarStandPossible =
        x === this.mapSize - 1 || // 맨 끝에 있다면 기둥 생성 못하므로 의미 없음.
        !this.arr[x + 1][y][0] || // 오른쪽에 기둥이 있는 게 맞는지
        this.arr[x + 1][y][1] || // 오른쪽에 보가 이어졌는지
        !y || // 바닥인지
        this.arr[x + 1][y - 1][0]; // 오른쪽 아래에 기둥이 있는지

      const isLeftFloorStandPossible =
        !x || // 맨 왼쪽이라면 true
        !y || // 맨 아래층이라도 true (그럴리는 없음)
        !this.arr[x - 1][y][1] || // 만약 애초부터 계산하지 않아도 된다면 true
        this.arr[x][y - 1][0] || // 현재 밑에 기둥이 있는지
        this.arr[x - 1][y - 1][0]; // 왼쪽 밑에 기둥이 있는지

      // 계산 시 맨 끝이면 의미가 없음.
      // 현재 위치 오른쪽 밑에 기둥이 있는지
      // 현재 위치 오른쪽 오른쪽 밑에 기둥이 있는지
      const isRightFloorStandPossible =
        x >= this.mapSize - 2 ||
        !this.arr[x + 1][y][1] ||
        this.arr[x + 1][y - 1][0] ||
        this.arr[x + 2][y - 1][0];

      return (
        isPillarStandPossible &&
        isRightPillarStandPossible &&
        isLeftFloorStandPossible &&
        isRightFloorStandPossible
      );
    } else {
      // pillar
      // 내 위에 기둥이 없거나, 기둥이 보에 받쳐져 있으면 가능.
      const overPillarStandPossible =
        !this.arr[x][y + 1][0] ||
        (x > 0 && this.arr[x][y + 1][1] && this.arr[x - 1][y + 1][1]) ||
        (this.arr[x][y + 2][1] && this.arr[x - 1][y + 2][1]);

      // 현재 보가 없거나, 지탱할 만한 뭔가가 있어야 한다.
      const nowFloorStandPossible = !this.arr[x][y][1] || this.arr[x][y + 1][1];

      // 왼쪽 보도 없거나, 버틸 수만 있다면 가능.
      const nowLeftFloorStandPossible =
        !x || !this.arr[x - 1][y][1] || this.arr[x - 1][y][0];

      return (
        overPillarStandPossible &&
        nowFloorStandPossible &&
        nowLeftFloorStandPossible
      );
    }
  }

  checkDeletePillarPossible(x, y) {
    const result = this.simulateDelete(x, y, 0);
    this.backupBeforeDelete(x, y, 0);

    return result;
  }

  checkDeleteFloorPossible(x, y) {
    const result = this.simulateDelete(x, y, 1);
    this.backupBeforeDelete(x, y, 1);

    return result;
  }

  updateBuildMap(x, y, buildCode, commandCode) {
    // 1 = delete => false, 0 = add => true
    this.arr[x][y][buildCode] = !!commandCode;
  }

  render(buildFrame) {
    buildFrame.forEach((command) => {
      const [x, y, buildCode, commandCode] = command;

      if (
        this.checkBuild(
          x,
          y,
          this.#BuildTypes[buildCode],
          this.#CommandTypes[commandCode]
        )
      ) {
        this.updateBuildMap(x, y, buildCode, commandCode);
      }
    });
  }

  getFinalBuildMaterials() {
    const buildMaterials = [];

    for (let i = 0; i < this.mapSize; i += 1) {
      for (let j = 0; j < this.mapSize; j += 1) {
        for (let buildCode = 0; buildCode < 2; buildCode += 1) {
          if (this.arr[i][j][buildCode]) {
            buildMaterials.push([i, j, buildCode]);
          }
        }
      }
    }

    return buildMaterials;
  }
}

const solution = (n, buildFrame) => {
  const buildMap = new BuildMap(n);
  buildMap.render(buildFrame);

  return buildMap.getFinalBuildMaterials();
};
class BuildMap {
  #PILLAR_CODE = 0;
  #FLOOR_CODE = 1;
  #COMMAND_ADD_CODE = 1;
  #COMMAND_DELETE_CODE = 0;

  #BuildTypes = Object.freeze({
    [this.#PILLAR_CODE]: '기둥',
    [this.#FLOOR_CODE]: '보',
  });

  #CommandTypes = Object.freeze({
    [this.#COMMAND_DELETE_CODE]: '삭제',
    [this.#COMMAND_ADD_CODE]: '추가',
  });

  constructor(n) {
    this.mapSize = n + 1;
    this.arr = Array.from(
      { length: this.mapSize },
      () => Array.from({ length: this.mapSize }, () => [false, false]) // pillar, floor(now -> right)
    );
  }

  checkBuild(x, y, buildType, commandType) {
    const commands = {
      [this.#CommandTypes[this.#COMMAND_DELETE_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]:
          this.checkDeletePillarPossible.bind(this, x, y),
        [this.#BuildTypes[this.#FLOOR_CODE]]:
          this.checkDeleteFloorPossible.bind(this, x, y),
      },
      [this.#CommandTypes[this.#COMMAND_ADD_CODE]]: {
        [this.#BuildTypes[this.#PILLAR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#PILLAR_CODE
        ),
        [this.#BuildTypes[this.#FLOOR_CODE]]: this.possibleAdd.bind(
          this,
          x,
          y,
          this.#FLOOR_CODE
        ),
      },
    };

    return commands[commandType][buildType]();
  }

  isValidPillar(x, y) {
    if (x < 0) return false;
    if (y < 0) return false;

    // 바닥에 설치할 경우
    if (y === 0) return true;

    // 한쪽 보 끝에 위치할 경우
    if (this.arr[x][y][1]) return true;
    if (x > 0 && this.arr[x - 1][y][1]) return true;

    // 다른 기둥 위에 있을 경우
    if (this.arr[x][y - 1][0]) return true;

    return false;
  }

  isValidFloor(x, y) {
    if (x < 0 || x >= this.mapSize - 1) return false;
    if (y <= 0) return false;

    // 한쪽 끝 부분이 기둥 위에 있는 경우
    if (this.arr[x][y - 1][this.#PILLAR_CODE]) return true;
    if (this.arr[x + 1][y - 1][this.#PILLAR_CODE]) return true;

    // 다른 보와 동시에 연결되어 있을 경우
    if (
      x &&
      this.arr[x - 1][y][this.#FLOOR_CODE] &&
      this.arr[x + 1][y][this.#FLOOR_CODE]
    )
      return true;

    return false;
  }

  possibleAdd(x, y, buildTypeCode) {
    if (this.arr[x][y][buildTypeCode]) return false;

    this.arr[x][y][buildTypeCode] = true;

    const result = (buildTypeCode ? this.isValidFloor(x, y) : this.isValidPillar(x, y));

    this.arr[x][y][buildTypeCode] = false;

    return result;
  }

  delete(x, y, buildCode) {
    this.arr[x][y][buildCode] = false;
  }

  backupBeforeDelete(x, y, buildCode) {
    this.arr[x][y][buildCode] = true;
  }

  checkDeletePillarPossible(x, y) {
    if (!this.arr[x][y][this.#PILLAR_CODE]) return false;

    this.delete(x, y, this.#PILLAR_CODE);

    // pillar
    // 내 위에 기둥이 있을 경우.
    const overPillarStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][this.#PILLAR_CODE] ||
      this.isValidPillar(x, y + 1);

    // 위쪽의 보가 없거나, 지탱할 만한 뭔가가 있어야 한다.
    const nowOverFloorStandPossible =
      y + 1 >= this.mapSize ||
      !this.arr[x][y + 1][1] ||
      this.isValidFloor(x, y + 1);

    // 왼쪽 보도 없거나, 버틸 수만 있다면 가능.
    const nowOverLeftFloorStandPossible =
      x - 1 < 0 ||
      y + 1 >= this.mapSize ||
      !this.arr[x - 1][y + 1][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y + 1);

    const result =
      overPillarStandPossible &&
      nowOverFloorStandPossible &&
      nowOverLeftFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#PILLAR_CODE);

    return result;
  }

  checkDeleteFloorPossible(x, y) {
    if (!this.arr[x][y][1]) return false;

    this.delete(x, y, this.#FLOOR_CODE);

    // floor
    // 만약 현재 위치에 기둥이 있다면 유효한지 체크
    const isPillarStandPossible =
      !this.arr[x][y][this.#PILLAR_CODE] || this.isValidPillar(x, y);

    // 현재의 오른쪽에 세워진 기둥도 유효한지 체크.
    const isRightPillarStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#PILLAR_CODE] ||
      this.isValidPillar(x + 1, y);

    // 현재의 왼쪽 보도 유효한지 체크
    const isLeftFloorStandPossible =
      x - 1 < 0 ||
      !this.arr[x - 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x - 1, y);

    // 현재의 오른쪽 보도 유효한지 체크
    const isRightFloorStandPossible =
      x + 1 >= this.mapSize ||
      !this.arr[x + 1][y][this.#FLOOR_CODE] ||
      this.isValidFloor(x + 1, y);

    const result =
      isPillarStandPossible &&
      isRightPillarStandPossible &&
      isLeftFloorStandPossible &&
      isRightFloorStandPossible;

    this.backupBeforeDelete(x, y, this.#FLOOR_CODE);

    return result;
  }

  updateBuildMap(x, y, buildCode, commandCode) {
    // 0 = delete => false, 1 = add => true
    this.arr[x][y][buildCode] = !!commandCode;
  }

  render(buildFrame) {
    buildFrame.forEach((command) => {
      const [x, y, buildCode, commandCode] = command;

      if (
        this.checkBuild(
          x,
          y,
          this.#BuildTypes[buildCode],
          this.#CommandTypes[commandCode]
        )
      ) {
        this.updateBuildMap(x, y, buildCode, commandCode);
      }
    });
  }

  getFinalBuildMaterials() {
    const buildMaterials = [];

    for (let i = 0; i < this.mapSize; i += 1) {
      for (let j = 0; j < this.mapSize; j += 1) {
        for (let buildCode = 0; buildCode < 2; buildCode += 1) {
          if (this.arr[i][j][buildCode]) {
            buildMaterials.push([i, j, buildCode]);
          }
        }
      }
    }

    return buildMaterials;
  }
}

const solution = (n, buildFrame) => {
  const buildMap = new BuildMap(n);
  buildMap.render(buildFrame);

  return buildMap.getFinalBuildMaterials();
};