프로그래머스 [Lv. 3] 기둥과 보 설치 {언어 : Python} [다시 풀어 보기]

문제 링크

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

프로그래머스

정답 코드

def solution(n, build_frame):
    visited = dict()
    def isGotten(nx, ny, a):
        return visited.get((nx, ny, a), 0)
    
    def check():
        for x, y, a in visited:
            if a:
                if isGotten(x, y-1, 0) or isGotten(x+1, y-1, 0) or (isGotten(x-1, y, 1) and isGotten(x+1, y, 1)):
                    continue
                return False
            else:
                if y == 0 or isGotten(x-1, y, 1) or isGotten(x, y, 1) or isGotten(x, y-1, 0):
                    continue
                return False
        return True
        
    for x, y, a, b in build_frame:
        if b:
            visited[(x, y, a)] = 1
            if not check(): 
                del visited[(x, y, a)]
        else:
            del visited[(x, y, a)]
            if not check():
                visited[(x, y, a)] = 1
    answer = sorted(list(visited.keys()))
    return answer

풀이 방법

1. 풀이는 의외로 간단하다.
2. 일단 기둥이나 보를 설치한다.
3. 유효한지 확인하고 유효하지 않으면 삭제한다.
4. 삭제도 마찬가지로 제거하고 시작한다.
5. 유효한지 확인하고 유효하지 않으면 다시 설치한다.
6. 마지막에 남은 visited의 key값만 모아서 정렬해서 반환하면 끝!

느낀점

• 어디서 봤는데 n이 2000정도면 n**2으로 풀어도 되므로 n**2풀이를 떠올려보라고 했던 것 같다.
• 계속 다시 풀어봐야 하는 문제들이 많아지는데 3렙 다 풀면 다시 풀어봐야겠다.