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

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

코딩테스트 연습 - 기둥과 보 설치

 

기둥과 보를 설치할 수 있는지, 삭제할 수 있는지를 문제를 보고 조건을 잘 만들어 주면 된다.

 

삭제의 경우, (x, y) 를 삭제했을 때 주위의 좌표들도 조건에 맞아야 삭제할 수 있다. 

(x, y) 를 삭제하려고 할 때, (x - 1, y + 1) 의 경우도 조건에 맞는지 비교를 해야하는데 이 부분을 놓쳐서 계속 실패했었다.

 

dic(dictionary) 를 이용하여 해당 좌표에 기둥이나 보가 설치되어 있으면 1, 그렇지 않으면 0 으로 dic 이 완성되면 dic[key] 가 1 인 key 값을 answer 에 넣어서 조건대로 정렬해주면 된다. 

 

from collections import defaultdict

def solution(n, build_frame):
    answer = []
    dic = defaultdict(int)
    
    for i in build_frame:
        x, y, M, D = i
        
        if D == 1:
            if condition(dic, x, y, M):
                dic[(x, y, M)] = 1       
        else:
            if dic[(x, y, M)] == 1:
                dic[(x, y, M)] = 0

                for j in [(0, 0), (-1, 0), (0, -1), (1, 0), (0, 1), (-1, 1)]:
                    for k in range(2):
                        x_, y_ = x + j[0], y + j[1]

                        if dic[(x_, y_, k)] == 1:
                            if not condition(dic, x_, y_, k):
                                dic[(x, y, M)] = 1
                                break

                    if dic[(x, y, M)] == 1: break
                                           
    for key in dic.keys():
        if dic[key] == 1:
            answer.append(list(key))
    
    answer = sorted(answer, key = lambda x : (x[0], x[1], x[2]))
    
    return answer

def condition(dic, x, y, M):
    answer = False
    
    if M == 0:
        if y == 0 or dic[(x, y-1, 0)] == 1 or dic[(x-1, y, 1)] == 1 or dic[(x, y, 1)] == 1:
            answer = True
    else:
        if dic[(x, y-1, 0)] == 1 or dic[(x+1, y-1, 0)] == 1 or (dic[(x-1, y, 1)] == 1 and dic[(x+1, y, 1)] == 1):
            answer = True
    
    return answer
    
print(solution(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]]