프로그래머스 레벨3 - 카카오 2020 기둥과 보 설치

문제주소

programmers.co.kr/learn/courses/30/lessons/60061

코딩테스트 연습 - 기둥과 보 설치

내 풀이

def solution(n, build_frame):
    answer = []
    column_layout = [[-1]*(n+1) for _ in range(n+1)]
    span_layout = [[-1]*(n+1) for _ in range(n+1)]
    for frame in build_frame:
        x, y, structure, construction = frame[0],frame[1],frame[2],frame[3]
        # 기둥인 경우 설치
        if structure == 0 and construction == 1 and column([x,y], column_layout, span_layout):
            column_layout[y][x] = 2
            answer.append([x,y,structure])
        # 보인 경우 설치
        if structure == 1 and construction == 1 and span([x,y], column_layout, span_layout):
            span_layout[y][x] = 2
            answer.append([x,y,structure])
        # 기둥 삭제의 경우
        if structure ==0 and construction == 0:
            column_layout[y][x] = -1
            if checkNineSides([x,y], span_layout,column_layout):
                answer.remove([x,y,structure])
            else:
                column_layout[y][x] = 2
        # 보 삭제의 경우
        if structure == 1 and construction ==0:
            span_layout[y][x] = -1
            if checkNineSides([x,y], span_layout,column_layout):
                answer.remove([x,y,structure])
            else:
                span_layout[y][x] = 2
    return sorted(answer, key=lambda x : (x[0],x[1],x[2]))

def checkNineSides(position, span_layout, column_layout):
    dx = [0,0, 0, 1, -1, 1,-1,1,-1]
    dy = [0,1, -1, 0, 0,1,-1,-1,1]
    for i in range(9):
        x = position[0] + dx[i]
        y = position[1] + dy[i]
        if span_layout[y][x] != -1 and span([x,y], column_layout, span_layout) == False:
            return False
        if column_layout[y][x] != -1 and column([x,y], column_layout, span_layout)== False:
            return False
    return True


def span(frame,  column_layout, span_layout):
  # 한쪽 끝이 기둥 위에(2가지 경우)
    if column_layout[frame[1]-1][frame[0]] != -1 or column_layout[frame[1]-1][frame[0]+1] != -1:
        return True
  # 양끝이 보 
    if span_layout[frame[1]][frame[0]-1] != -1 and span_layout[frame[1]][frame[0]+1] != -1:
        return True
    return False


def column(frame, column_layout, span_layout):
  # 바닥에 기둥
    if frame[1] == 0:
        return True
  # 기둥 위에 기둥
    if column_layout[frame[1]-1][frame[0]] != -1:
        return True
  # 보 끝에 기둥 (2가지)
    if span_layout[frame[1]][frame[0]-1] != -1 or span_layout[frame[1]][frame[0]] != -1:
        return True
    return False

하.. 너무 오래 걸렸다.😂 모든 케이스에 대해서 확인해줘야하는 문제의 요구사항을 빠뜨리면 안 되는 그런 문제였다. 다양한 케이스를 헷갈리지 않고 잘 작성하냐가 문제의 핵심이었다고 생각한다. 처음에는 layout도 하나로 작성하다가 한 점에 보와 기둥이 같이 설치되는 경우가 해결이 안 되서 나누게 되었다.

다른 사람 풀이

# 이 코드의 출처는 나동빈님 깃허브 입니다.
# : https://github.com/ndb796/python-for-coding-test/blob/master/12/6.py 

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: # 설치된 것이 '기둥'인 경우
            # '바닥 위' 혹은 '보의 한쪽 끝 부분 위' 혹은 '다른 기둥 위'라면 정상
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            return False # 아니라면 거짓(False) 반환
        elif stuff == 1: # 설치된 것이 '보'인 경우
            # '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                continue
            return False # 아니라면 거짓(False) 반환
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame: # 작업(frame)의 개수는 최대 1,000개
        x, y, stuff, operate = frame
        if operate == 0: # 삭제하는 경우
            answer.remove([x, y, stuff]) # 일단 삭제를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
        if operate == 1: # 설치하는 경우
            answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거
    return sorted(answer) # 정렬된 결과를 반환

이것이 취업을 위한 코딩테스트다(책)에서 본 풀이는 solution과 possible 두 메소드로 나눠서 실행한다. solution에서 삭제하는 경우, 설치하는 경우로 나눈다. possible에서는 기둥과 보로 나누고 확인한다. 일단, solution에서 설치, 삭제를 해서 answer에 넣어준 뒤, answer의 모든 내용에 대해 possible에서 확인한다. boolean 값을 return 해준다. false라면 solution에서 remove해서 answer에서 제거해준다. 따라서 조건에 해당되는 answer만이 남게 되는 것이다. 나처럼 layout을 설정한 것이 아니라 [x-1,y,1] in answer 이런 케이스 형식으로 answer를 가지고 체크한다. x, y 값을 변경하지 않고 그대로 사용할 수 있는 것도 장점이었다.

정리

다양한 케이스를 어떻게 예외없이 나누어 확인할 수 있냐가 포인트였다고 생각한다. 큰 분기를 가지고 나누고 거기서 세분화되는 분기를 만들어 체크해 나가는 것이 좋다. 문제가 요구하는 모든 조건을 누락하지 않고 구현해 내는 것이 중요하다. 다양한 분기가 작성될 때 어떻게 잘 구조화해나가느냐가 중요한 것 같다. 조건이 맞으면 설치이어도 설치한 뒤 안 맞으면 제거하는 방식으로 진행하는 것도 좋다. 잘 안 풀리면 반대의 경우로 생각해보자!😀 분기가 많아질 때 어떻게 하면 공통적으로 활용할 수 있을까를 생각해야 한다.