[프로그래머스] 기둥과 보 설치

델리만쥬 디퓨저·2024년 10월 21일

구현 알고리즘 파이썬

알고리즘

목록 보기

13/15

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

문제 분석

기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 함
보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 함

핵심 아이디어

기둥과 보를 설치하는 것이 가능한지 확인하는 함수

기둥
- 바닥 위에 있는지
- 보의 한쪽 끝 부분 위에 있는지
- 다른 기둥 위에 있는지
보
- 한쪽 끝 부분이 기둥 위에 있는지
- 양쪽 끝 부분이 다른 보와 동시에 연결되어 있는지

def possible(result):
    ROW = 1
    COL = 0
    for x, y, a in result:
        if a == COL:
            if y != 0 and (x, y - 1, COL) not in result and (x - 1, y, ROW) not in result and (x, y, ROW) not in result: \
                    return False
        else:
            if (x, y - 1, COL) not in result and (x + 1, y - 1, COL) not in result and not (
                    (x - 1, y, ROW) in result and (x + 1, y, ROW) in result):
                return False
    return True

실행 흐름

x, y, a, build를 받는다
x, y, a는 하나로 묶고, build를 통해 어떤 작업을 할 지 결정한다
build가 0이라면 설치이므로 answer에 x, y, a를 answer에 저장한다
저장 후 answer의 가능 여부를 검사하고, 실패하면 저장한 값을 삭제한다
build가 0이 아니고 x, y, a가 저장한 값에 있다면, 삭제한다
삭제 후 answer의 가능 여부를 검사하고, 실패하면 삭제한 값을 복원한다
이후 저장된 answer의 튜플을 리스트로 변환하고, 정렬하여 반환한다.

전체 코드

def possible(result):
    ROW = 1
    COL = 0
    for x, y, a in result:
        if a == COL:
            if y != 0 and (x, y - 1, COL) not in result and (x - 1, y, ROW) not in result and (x, y, ROW) not in result: 
                    return False
        else:
            if (x, y - 1, COL) not in result and (x + 1, y - 1, COL) not in result and not (
                    (x - 1, y, ROW) in result and (x + 1, y, ROW) in result):
                return False
    return True


def solution(n, build_frame):
    answer = []
    for x, y, a, build in build_frame:
        item = (x, y, a)
        if build:
            answer.append(item)
            if not possible(answer):
                answer.remove(item)
        elif item in answer:
            answer.remove(item)
            if not possible(answer):
                answer.append(item)

    answer = [list(x) for x in sorted(answer, key=lambda item: (item[0], item[1], item[2]))]
    return sorted(answer)