비움

카카오 테스트:기둥과 보 설치

카카오 테스트:기둥과 보 설치

by 유정민 3 min read

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

이 문제는 문제의 효율성 고려나 어려운 개념을 요구하는 게 아니라
주어진 복잡한 instructions을 코드로 구현 할 수 있는 지를 묻는 문제입니다.
따라서 전체과정을 도식화하는 능력과 깔끔한 코드를 짜는게 핵심이라고 생각합니다.

핵심 개념:

  1. Matrix rotation
  2. BitMask

TIP:

첫 번째, 적당한 Matrix rotation를 이용해서 문제에서 주어지는 Matrix의 좌표를
우리가 평소에 사용하는 Matrix의 좌표로 바꾸어 놓고, 문제를 생각하면 좀 더 수월합니다.
몇 가지의 경우를 종이에 적어보시면, 어떻게 치환 할 지 패턴이 보이실 겁니다.
Ex) n = 5일떄, (0,0) -> (5,0), (0,3) -> (2, 0), (3,4) -> (1, 3)
※ 앞: 문제에서 주어진 좌표, 뒤: 우리가 실제 사용할 좌표

두 번째, Bit maninpuation을 이용하면, 설치, 삭제 또는 현재 상태까지 나타낼 수 있습니다.
OR: 설치, XOR: 삭제, xxxx: 앞에 두 개의 digit은 기둥의 상태, 뒤에 두 개의 digits은 보의 상태
1: 있다 0: 없다로 생각하고 아래와 같이 생각하면 편합니다.
Ex) 0000: 아무것도 없다, 1000: 기둥 아랫부분만 있다. ,1100: 기둥 아랫부분 과 기둥 윗부분이 있다.
1011: 기둥 아랫부분 과 보의 왼쪽과 보의 오른쪽이 있다., 0001: 보의 오른쪽만 있다.

마지막으로, 이 문제는, 설치보단 삭제 부분이 조금 까다롭습니다.
혹시 테스트가 13번 이후로 다 틀린다면, 삭제 부분에서 문제가 있을 확률이 큽니다.

풀이법

저 같은 경우 이걸 아래와 같은 과정을 도식화하여 풀었습니다.
워낙 코드가 길어, 제 코드 리딩은 도움이 안될 거 같습니다.

  1. 삭제할 좌표에 실제로 보 또는 기둥이 존재하는 지 판단 (없을시 return)
  2. 일단 삭제한다고 가정
  3. 영향을 끼칠 좌표들의 유효성 검사
  4. 영향을 끼칠 좌표들이 모두 유효하다면 삭제 그대로 진행
  5. 하나라도 유효하지 않으면, 다시 삭제했던 구조물 재설치

구현 by Python

import os
import sys


def pillar_alive(coord, matrix):
    x, y = coord
    pillar_start, pillar_end, bar_start, bar_end = Checker(matrix[x][y])

    if pillar_end or bar_start or bar_end: return True
    else: return False

def bar_alive(coord, matrix, ttype):
    x, y = coord

    C_pillar_start, C_pillar_end, C_bar_start, C_bar_end = Checker(matrix[x][y])
    if ttype == 'left':
        L_pillar_start, L_pillar_end, L_bar_start, L_bar_end = Checker(matrix[x][y-1])
        if C_pillar_end or L_pillar_end: return True
        elif C_bar_start and L_bar_end: return True
        else: return False

    elif ttype == 'right': # given is start
        R_pillar_start, R_pillar_end, R_bar_start, R_bar_end = Checker(matrix[x][y+1])
        if C_pillar_end or R_pillar_end: return True
        elif C_bar_end and R_bar_start: return True
        else: return False
    else:
        print('IMPOSSIBLE')


def Checker(value) -> list:
    #result = [pillar's start, pillar's end, bar's start, bar's end]
    _bit = '{:04b}'.format(value)
    result = []

    for _ in _bit:
        if _ == '0': result.append(False)
        elif _ == '1': result.append(True)
        else: print("Impossible: ", _)
    return result

def CoordSwapper1(coord, matrix): # problemSetting coord -> build_it coord
    x, y = coord
    swapped_x = len(matrix) - 1 - y
    swapped_y = x
    return (swapped_x, swapped_y)

def CoordSwapper2(coord, matrix): # built_in coord -> problemSetting coord
    x, y = coord
    swapped_x = y
    swapped_y = len(matrix) - 1 - x
    return (swapped_x, swapped_y)

def remove_bar(coord, matrix):
    x, y = coord
    L_pillar_start, L_pillar_end, L_bar_start, L_bar_end = Checker(matrix[x][y])
    R_pillar_start, R_pillar_end, R_bar_start, R_bar_end = Checker(matrix[x][y+1])

    if not L_bar_start: return
    #remove
    matrix[x][y]^= 2; matrix[x][y+1]^= 1

    L_pillar_TEST = True if (not L_pillar_start) or pillar_alive((x,y), matrix) else False
    R_pillar_TEST = True if (not R_pillar_start) or pillar_alive((x, y+1), matrix) else False
    L_bar_TEST = True if (not L_bar_end) or bar_alive((x, y), matrix, 'left') else False
    R_bar_TEST = True if (not R_bar_start) or bar_alive((x, y+1), matrix, 'right') else False

    if L_pillar_TEST and R_pillar_TEST and L_bar_TEST and R_bar_TEST: return
    else: matrix[x][y]|= 2; matrix[x][y+1]|= 1 #reinstall


def remove_pillar(coord, matrix):
    x, y = coord
    D_pillar_start, D_pillar_end, D_bar_start, D_bar_end = Checker(matrix[x][y])
    U_pillar_start, U_pillar_end, U_bar_start, U_bar_end = Checker(matrix[x-1][y])

    if not D_pillar_start: return
    #remove
    matrix[x][y]^= 8; matrix[x-1][y]^= 4

    U_pillar_TEST = True if (not U_pillar_start) or pillar_alive((x-1, y), matrix) else False
    L_bar_TEST = True if (not U_bar_end) or bar_alive((x-1, y), matrix, 'left') else False
    R_bar_TEST = True if (not U_bar_start) or bar_alive((x-1, y), matrix, 'right') else False

    if U_pillar_TEST and L_bar_TEST and R_bar_TEST: return
    else: matrix[x][y]|= 8; matrix[x-1][y]|= 4 # reinstall


def install_pillar(coord, matrix):
    x, y = coord
    pillar_start, pillar_end, bar_start, bar_end = Checker(matrix[x][y])

    if x == len(matrix)-1 or bar_start or bar_end or pillar_end:
        matrix[x][y] |= 8
        matrix[x-1][y] |= 4

def install_bar(coord, matrix):
    x, y = coord
    L_pillar_start, L_pillar_end, L_bar_start, L_bar_end = Checker(matrix[x][y])
    R_pillar_start, R_pillar_end, R_bar_start, R_bar_end = Checker(matrix[x][y+1])

    if L_pillar_end or R_pillar_end or (L_bar_end and R_bar_start):
        matrix[x][y] |= 2
        matrix[x][y+1] |= 1

def show_all(matrix, res):
    n = len(matrix)

    for x in range(n):
        for y in range(n):
            pillar_start, pillar_end, bar_start, bar_end = Checker(matrix[x][y])
            _x, _y = CoordSwapper2( (x, y), matrix)
            if pillar_start: res.append([_x,_y,0])
            if bar_start: res.append([_x,_y,1])
    return

def solution(n, build_frame):

    res = []; matrix = [[0]*(n+1) for i in range(n+1)]

    for op in build_frame:
        x, y, a, b = op

        _x, _y = CoordSwapper1((x,y), matrix)
        if a == 0 and b == 0: remove_pillar((_x,_y), matrix)
        elif a == 0 and b == 1: install_pillar((_x,_y), matrix)
        elif a == 1 and b == 0: remove_bar((_x,_y), matrix)
        elif a == 1 and b == 1: install_bar((_x,_y), matrix)
        else: print("IMPOSSIBLE: ", op)

    show_all(matrix, res)
    res.sort()

    return res