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

1. 문제 - 프로그래머스 기둥과 보 설치

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

 

❌ 틀린 풀이

- 테스트 케이스는 통과하는데 제출했을 때 테스트 6, 7만 통과함

import copy

def solution(n, build_frame):
    board = [[-1] * (n+1) for _ in range(n+1)]
    
    def isValid(board):
        for i in range(n+1):
            for j in range(n+1):
                if board[i][j] == 0:    # 기둥일 경우
                    # 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
                    if not (j == 0 or (0<=j-1<=n and board[i][j-1] == 0) or (0<=i-1<=n and board[i-1][j] == 1)):
                        return False
                elif board[i][j] == 1:    # 보일 경우
                    # 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
                    if not ((0<=j-1<=n and board[i][j-1] == 0) or (0<=i+1<=n and 0<=j-1<=n and board[i+1][j-1] == 0) or (0<=i-1<=n and board[i-1][j] == 1)):
                        return False
                    
        return True

    for build in build_frame:
        # a 값이 0은 기둥, 1은 보
        # b 값이 0은 삭제, 1은 설치
        x, y, a, b = build
        
        temp = copy.deepcopy(board)   # 조건을 판단하기 위해 복사본 생성
        if b == 1:         # 설치일 경우 board에 할당
            temp[x][y] = a
        else:   # 삭제할 경우 -1 할당
            temp[x][y] = -1
            
        if isValid(temp):    # 유효한지 따져보고, 유효하면 해당 temp 보드를 할당
            board = temp
            
    answer = []
    for i in range(n+1):
        for j in range(n+1):
            if board[i][j] != -1:
                answer.append((i, j, board[i][j]))
    return sorted(answer, key=lambda x:(x[0], x[1], x[2]))

 

1시간 넘게 이것저것 시도해보다가 도저히 어디가 틀린지 잘 모르겠어서 다른 사람들의 풀이를 보고 이해해보고자 했다.

- 여기서 중요한 점을 알게 되었는데, 문제 조건에서 "x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다."

즉 x, y가 겹칠 수도 있다는 의미이다. 나는 한 좌표에는 무조건 기둥 혹은 보가 와야 한다고 가정하고 문제를 풀었다. (temp[x][y] = a 이부분)

 - 따라서 보의 좌표와 기둥의 좌표들을 따로 들고다니면서 관리해야한다.

 

✅ 다른사람 풀이를 참고해서 다시 풀이한 내 풀이

def solution(n, build_frame):
    
    def isValid():
        for x, y in gidung:
            # 바닥 위에 있거나, 다른 기둥 위에 있거나, 보의 한쪽 끝부분에 있거나
            if not (y == 0 or (x, y-1) in gidung or (x-1, y) in bo or (x, y) in bo):
                return False

        for x, y in bo:
            # 한쪽 끝부분이 기둥 위에 있거나, 양쪽 끝부분이 다른 보와 연결되어 있어야함
            if not ((x, y-1) in gidung or (x+1, y-1) in gidung or (x+1, y) in bo and (x-1, y) in bo):
                return False

        return True
    
    gidung = set()
    bo = set()
    
    for build in build_frame:
        # a: 0 기둥 1 보
        # b: 0 삭제 1 설치
        x, y, a, b = build
        
        if b == 1:
            if a == 0:
                gidung.add((x, y))
                if not isValid():
                    gidung.remove((x, y))
            else:
                bo.add((x, y))
                if not isValid():
                    bo.remove((x, y))
        else:
            if a == 0:
                gidung.remove((x, y))
                if not isValid():
                    gidung.add((x, y))
            else:
                bo.remove((x, y))
                if not isValid():
                    bo.add((x, y))    
    
    answer = []
    for x, y in gidung:
        answer.append([x, y, 0])
    for x, y in bo:
        answer.append([x, y, 1])
        
    return sorted(answer)

 

- set를 활용한 이유는 O(1)의 시간복잡도로 add, remove가 가능하기 때문이다. 따라서 set를 활용하여 좌표를 관리한다.

- 기둥의 조건중 내가 놓친 부분이 2개 있다.

1) "보의 한쪽 끝 부분 위에 있거나" 이다. -->  x, y 좌표가 보 좌표 리스트에도 있는지 검사해야한다.

2) "양쪽 끝부분이 다른 보와 연결되어 있어야 한다" --> (x-1, y)와 (x+1, y)가 보 좌표 리스트에도 있는지 검사해야한다.

- 설치할 때는 일단 넣어봤다가, 좌표들이 기준에 맞지 않으면 다시 빼주고 (조건을 만족하지 않으므로 무시), 제거할 때는 일단 제거했다가, 좌표들이 기준에 맞지 않으면 다시 넣어준다 (조건을 만족하지 않으므로 무시)