[Programmers/Python] 기둥과 보 설치

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

프로그래머스

💭풀이 과정

1. 문제 조건

• input
  • n: 벽면의 크기 (5≤ n ≤ 100인 자연수)
  • build_frame: 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열
    • [x, y, a, b]
    • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표]
    • a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보
    • b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치
    • 바닥에 보를 설치하는 경우는 없다.
  • 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제한다.
  • 기둥과 보의 길이는 1이다.
    • 기둥은 (1) 바닥 위에 있거나 (2) 보의 한쪽 끝 부분 위에 있거나, 또는 (3) 다른 기둥 위에 있어야 한다.
    • 보는 (1) 한쪽 끝 부분이 기둥 위에 있거나, 또는 (2) 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 한다.
• output
  • return: 모든 명령어를 수행한 후 구조물의 상태를 담은 2차원 배열
  • 2차원 배열로 원소는 [x, y, a] 형식이다.
  • x, y는 기둥과 보의 교차점이며, [가로 좌표, 세로 좌표] 형태
  • a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보
  • 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음
  • return 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬
  • x, y 좌표가 모두 같은 경우 기둥이 보보다 앞에 오도록 한다.

[풀이]

• build_frame에서 하나씩 꺼내 명령을 수행한다.
  • 기둥/보일 때, 설치/삭제일 때 경우에 따라 수행했을 때 answer에 있는 기둥과 보가 계속 조건을 유지하는지 검사한다.
  • 조건에 만족하면 해당 좌표와 구조물을 [x,y,a] 형태로 answer에 추가(설치) 혹은 삭제(삭제)한다.
• answer를 출력 조건에 맞게 정렬한다.

🛠️코드

def solution(n, build_frame):
    answer = []
    
    for info in build_frame:
        x, y, a, b = info
        
        # # 삭제일 때
        if b == 0:                  
            answer.remove([x,y,a])  # 해당 구조물 삭제
            if check(answer):       # 삭제 가능한지 판단 
                continue
            answer.append([x,y,a])
        # 설치일 때
        if b == 1:   
            answer.append([x,y,a])  # 해당 구조물 설치
            if check(answer):       # 설치 가능한지 판단
                continue
            answer.remove([x,y,a])
            
    return sorted(answer)

# 기둥과 보의 설치 가능 여부
def check_condition(answer):
    for x,y,a in answer:
        # 기둥일 때
        if a == 0:
        # 기둥이 바닥 위 or 다른 기둥 위 or 보의 한쪽 끝 
            if y == 0 or [x,y-1,0] in answer or [x,y,1] in answer or [x-1,y,1] in answer:
                continue
            return False
        # 보일 때
        else:
            # 보의 한쪽 끝이 기둥 위 or 양쪽 끝이 동시에 다른 보에 연결
            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
    return True

🔑어려웠던 부분

다 구현해보면 정말 간단한데,

• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제한다.

위의 조건을 유념하여 조건식을 작성하는 것이 중요하다.

✍🏻회고 & 배운 점

리스트에 특정값을 삭제하는 list.remove() 함수를 사용하는 것을 두려워했다. 그 이유는 해당 함수의 시간복잡도가 O(n)이기 때문이다. 그래서 remove 함수를 안쓰고 어떻게 효율적으로 구현할지 고민하는 시간이 길었다.

 

dictionary를 사용하여 key를 (x,y) 좌표로 두고, value를 [0,0] 으로 하여 value[0]은 기둥의 유무, value[1]은 보의 유무를 나타내도록 하려했다. 그렇게 하면 삭제할 때 비교적 시간이 덜 소요될 것이라고 생각했다. 하지만 이렇게 하면 나중에 answer에 값을 넣을 때 후처리가 좀 복잡(귀찬)할 것 같았다.

 

추가적으로 list.remove()를 그냥 사용한 이유는 어차피 answer 길이의 최댓값은 build_frame의 길이이며 즉, 1이상 1,000이하이기 때문에 시간복잡도 측면에서도 나쁘지 않을 것이라고 판단하였다.