[프로그래머스] 기둥과 보 설치 (파이썬)

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

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

---

각 작업을 기존의 구조물에 적용시키고, 건축물이 규칙을 만족하지 않는다면 작업을 취소하는 순서로 진행합니다.

 

* solution

    - 작업이 수행될 때마다 기존에 존재하는 구조물에 적용시키고 유효성을 확인합니다

    - 유효하지 않다면 작업을 취소합니다

    - 문제 요구사항에 따라 x좌표, y좌표 순서대로 우선순위를 정하여 정렬합니다

 

* is_valid

    - 기둥인 경우, 아래 4개의 조건 중 하나를 만족해야 합니다

        1. 바닥인 경우

        2. 보가 왼쪽에 존재하는 경우

        3. 보가 현재 위치에 존재하는 경

        4. 기둥이 아래에 존재하는 경우 

    - 보인 경우, 아래의 3개 조건을 만족해야 합니다

        1. 기둥이 우측에 존재하는 경우

        2. 기둥이 아래에 존재하는 경우

        3. 양쪽에 보가 존재하는 경우

기둥을 위한 규칙

보를 위한 규칙

def is_valid(lst):
    for l in lst:
        x, y, a = l
        # pillar
        if a == 0:
            # floor
            if not y:
                continue
            # beam left
            if (x - 1, y, 1) in lst:
                continue
            # beam here
            if (x, y, 1) in lst:
                continue
            # pillar below
            if (x, y - 1, 0) in lst:
                continue
            break
        # beam
        else:
            # pillar right
            if (x + 1, y - 1, 0) in lst:
                continue
            # pillar below
            if (x, y - 1, 0) in lst:
                continue
            # between beam
            if (x - 1, y, 1) in lst and (x + 1, y, 1) in lst:
                continue
            break
    else:
        return True
    return False


def solution(n, build_frame):
    answer = []
    for build in build_frame:
        x, y, a, b = build
        if b:
            # installation valid
            answer.append((x, y, a))
            if not is_valid(answer):
                answer.remove((x, y, a))
        else:
            # demolition valid
            answer.remove((x, y, a))
            if not is_valid(answer):
                answer.append((x, y, a))
    answer.sort(key=lambda x: (x[0], x[1], x[2]))
    return answer