[이것이 코딩 테스트다 with Python] Chapter 12. 구현 - 기둥과 보 설치

< 기둥과 보 설치 >

 

💬 문제 설명

빙하가 깨지면서 스노우타운에 떠내려 온 "죠르디"는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. "죠르디"는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다.
....

 

입력 (n)	입력(build_frame)	출력(result)
5	[[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]	[[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]
5	[[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]]	[[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

💬 입력 조건

• n ( 5 ≤ n ≤ 100. n은 자연수 ) 
• build_frame의 세로(행) ( 1 ≤ 행 ≤ 1,000 )
• build_frame의 가로(열) ( 1 ≤ 열 ≤ 4 )
• build_frame의 원소 x, y, a, b
  
  
  • x, y는 기둥, 보를 설치할 좌표 [ 가로, 세로 ]
  • a는 구조물의 종류 ( 0은 기둥, 1은 보 )
  • b는 구조물 설치여부 ( 0은 삭제, 1은 설치 )

< 기둥과 보 설치 및 삭제 >

💬 출력 조건

• [x, y, a ] 형테 [ 가로, 세로, 구조물의 종류 ] 의 2차원 배열
• x의 오름차순, y의 오름차순, 구조물도 오름차순

---

✍ 문제요약

기둥과 보를 주어진 제한 사항에 맞춰서 설치 및 삭제 했을 때 최종적으로 만들어지는 구조물의 형태를 2차원 배열로 반환해야한다. 기둥의 경우 바닥 or 보의 한쪽 끝 부분 or 다른 기둥 위에 설치 및 삭제 가능하다. 보의 경우 한쪽 끝이 기둥 위 or 양쪽 끝 부분이 다른 보 일 때 설치 및 삭제 가능하다. 주어진 build_frame을 가지고 설치와 삭제가 마무리 된 후 최종 상태를 구하라.

💯 문제링크

프로그래머스의 "기둥과 보 설치"와 동일한 문제이다.

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

프로그래머스

---

✅  문제 풀이

n + 1  * n + 1 크기의 빈 배열을 만들어 기둥, 보를 표시하려 했으나 표시가 겹치는 부분에서 문제가 생긴다고 생각하여 다른사람의 코드를 보고 문제를 풀었다.

 

• set을 활용해서 기둥과 보가 설치 되는 경우에 set에 담아주는 방식으로 구현했다. ( list도 가능은 하나 set이 훨씬 빠르다 )
• 설치와 삭제 모두 set에 add 또는 append를 해주고 is_right 함수를 통해 가능 여부를 판단한다.
• is_right 함수
  
  
  • set에 있는 배열을 반복문으로 돌린다.
  • 기둥인 경우 바닥 or 보의 한쪽 끝 부분 or 다른 기둥 위 중 하나에도 성립되지 않으면 설치 or 삭제 불가

y 바닥		( x,  y - 1,  0 ) 다른 기둥 위
( x,  y,  1 ) 보의 왼쪽 끝		( x - 1,  y,  1 ) 보의 오른쪽 끝

 

• 보인 경우 한쪽 끝이 기둥 위 or 양쪽 끝 부분 둘다 다른 보 중 하나에도 성립되지 않으면 설치 or 삭제 불가

( x,  y - 1,  0 )  왼쪽 끝이 기둥		( x + 1,  y - 1,  0 ) 오른쪽 끝이 기둥
( x - 1,  y,  1 ) 왼쪽에 다른 보		( x + 1,  y,  1 ) 오른쪽에 다른

 

def solution(n, build_frame):
    built = set()
    
    def is_right():
        for x, y, a in built:
            
            if not a : # 기둥
                if y and (x, y-1, 0) not in built:
                    if (x, y, 1) not in built and (x-1, y, 1) not in built:
                        return False
                
            else: # 보
                if (x, y-1, 0) not in built and (x + 1, y - 1, 0) not in built:
                    if (x - 1, y, 1) not in built or (x + 1, y, 1) not in built:
                        return False
        return True
    
    for x, y, a, b in build_frame:
        if b: # 설치
            built.add((x, y, a))
            if not is_right():
                built.remove((x, y, a))
            
        else : # 삭제
            built.remove((x, y, a))
            if not is_right():
                built.add((x, y, a))
    
    return sorted(built)