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

🔗 Link

https://school.programmers.co.kr/learn/courses/30/lessons/60061?language=python3

프로그래머스

 

🧩 Source Code

'''
기둥과 보를 설치 및 삭제할 수 있는 환경인지 체크
있다면 실행 없다면 복구
'''
def solution(n, build_frame):
    made = []
    
    def can_build(x,y,a):
        if a == 0:  # 기둥
            return y == 0 or [x, y - 1, 0] in made or [x - 1, y, 1] in made or [x, y, 1] in made
        else:  # 보
            return ([x, y - 1, 0] in made or [x + 1, y - 1, 0] in made or
                    ([x - 1, y, 1] in made and [x + 1, y, 1] in made))
    
    def is_valid_structure():
        for x, y, a in made:
            if not can_build(x, y, a):
                return False
        return True

    for x,y,a,b in build_frame:
        # 삭제
        if b == 0 :
            made.remove([x,y,a])
            if not is_valid_structure():
                made.append([x,y,a])
        # 설치
        if b == 1 :
            made.append([x,y,a])
            if not is_valid_structure():
                made.remove([x,y,a])

    return sorted(made, key = lambda x : (x[0], x[1], x[2]))

---

 

📝 Commentary

시간 복잡도는 박살이 났을 것 같은 코드이다. 배열안에서 remove, in 연산자를 사용하는 것은 선호하는 방식이 아니지만 제일 직관적으로 작성될 수 있어서 선택을 했다.

 

build_frame을 순회하면서

삭제 -> 삭제하고 가능한지 체크 -> 유효하지 않다면 다시 복구

설치 -> 설치하고 가능한지 체크 -> 유효하지 않다면 다시 복구

 

이런 로직이고 기둥과 보를 설치하는 기준은 문제에서 주어진대로 구현을 했다.

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

 

---