기둥과 보 설치

문제

2020 KAKAO BLIND RECRUITMENT
https://school.programmers.co.kr/learn/courses/30/lessons/60061

문제 요약

2차원 벽면의 크기 n과 [[x, y, 기둥 or 보, 설치 or 삭제], ...]가 주어진다.
주어진 입력값으로 기둥과 보를 만들어서 건물을 만든다.
아래의 조건을 만족하도록 건물을 만들어서 [[x, y, 기둥 or 보], ...] 의 값을 나타내야 하는 문제

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

풀이과정

시뮬레이션 문제 이기 때문에 주어진 조건만 따르면 쉽게 구현할 수 있다.

나는 우선 주어진 입력 리스트를 도는 함수 하나와, 현재의 상태가 조건을 만족하는 지 체크하는 함수를 만들었다.

입력값이 1000 개정도 되기 때문에 O(N2) 이상으로 풀어도 되기 때문에 함수 두개다 처음부터 다 순회하는 형태로 코드를 짰다

✅ 현재의 상태를 체크할 때는 결과 리스트 [[x, y, 기둥 or 보], ...]를 전부 순회하며
예를 들어 기둥의 조건을 보면

• "바닥위에 있거나"는 y == 0
• "보의 한쪽 끝 부분 위에 있거나"는 [x - 1, y, 1], [x , y, 1]가 결과 값 안에 있을때
• "다른 기둥 위에 있어야 한다"는 [x, y - 1, 0]이 결과 값 안에 있을 떄

을 만족하지 않을 때 False를 반환해 줬다.

✅ 주어진 입력리스트를 순회 할 때
설치하는 경우에는 우선 설치하고 유효하지 않으면 다시 삭제한다.

삭제하는 경우에는 우선 삭제하고 유효하지 않으면 다시 설치한다.

의 과정을 거친뒤에

정렬해서 결과값과 같은 형태로 나타냈다.

코드

def check(answer):
    for x, y, a in answer:
        if a == 0:
            # 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
            if y == 0 or [x - 1, y, 1] in answer or [x , y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            else:
                return False
        if a == 1:
            # 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
            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
            else:
                return False
    return True
def solution(n, build_frame):
    answer = []
    # a 0기둥 1보, b 0삭제 1설치
    for x, y, a, b in build_frame:
        if b == 1: # 설치
            answer.append([x, y, a])
            if not check(answer):
                answer.remove([x, y, a])
        else: 
            answer.remove([x, y, a])
            if not check(answer):
                answer.append([x, y, a])

    answer.sort()
    return answer