기둥과 보 설치(2020 Kakao) 정리 및 코드

기둥과 보 설치

프로그래머스 Level3: https://school.programmers.co.kr/learn/courses/30/lessons/60061

Edge case

항상 주의해야하는 항목

1. 좌표 수정

• 좌표 수정(x-1, y-1)에는 항상 범위 체크할 필요가 있음 (이 문제에선 아님)

2. 문제 조건

• 매번 조건을 꼼꼼히 확인할 필요가 있음
• 여기서는 배열식 표현에 메일필요가 없음
• 그냥 데카르트 좌표계 그대로 진행해도 문제될게 없음
• 탐색시간이 많이 걸리긴 하나, 이 문제는 실행시간이 5초로 넉넉하므로 $O(N^3)$의 복잡도까지 가능

---

Code

• 처음 풀이는 2차원 배열에 저장하는 방식으로 풀었었는데 너무 복잡하여 생략하였다.
• 2차원 배열을 사용할 필요없이 answer 배열만 가지고도 해결가능한 Case!

# 기둥과 보 설치
# https://school.programmers.co.kr/learn/courses/30/lessons/60061
# 12:20
"""
* 글 읽는데 시간투자 많이 하기
"""

COL = 0
PANEL = 1

DLT = 0
INS = 1

def check(answer):
    for x, y, stuff in answer:
        if stuff == COL:
            # 바닥 위 / 다른 보 위 / 기둥 위
            if y == 0 or [x-1, y, PANEL] in answer or [x, y, PANEL] in answer or [x, y-1, COL] in answer:
                continue
            return False
        elif stuff == PANEL:
            # 기둥 위 / 보와 보 사이
            if [x, y-1, COL] in answer or [x+1, y-1, COL] in answer or (([x-1, y, PANEL] in answer) and ([x+1, y, PANEL] in answer)):
                continue
            return False
    return True

def solution(n, build_frame):
    answer = []
    for x, y, stuff, op in build_frame:
        if op == INS:
            answer.append([x, y, stuff])
            if not check(answer): answer.remove([x, y, stuff])
        elif op == DLT:
            answer.remove([x, y, stuff])
            if not check(answer): answer.append([x, y, stuff])
    answer.sort()
    return answer