Q12. 기둥과 보 설치 (2020 카카오 기출)

코딩테스트 연습 - 기둥과 보 설치 | 프로그래머스 (programmers.co.kr)

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

 

구현 문제다.

좌표를 잘 생각하면서 하면 그리 어렵지는 않을거같다.

내가보기에 카카오 구현문제의 최고봉은 '블록 이동하기'인거같음.

문제의 기둥과 보가 있을 수 있는 조건을 잘 보고

특정 좌표 x,y에 기둥 혹은 보를 설치할 때 어느 좌표에 뭐가 있어야 되는지를 잘 나타내면 될거같다.

예를 들어 x,y에 기둥을 설치하려면

(x,y)에 보가 있거나

(x-1,y)에 보가 있거나

y=0이거나

(x,y-1)에 기둥이 있어야 한다.

이런걸 그대로 정리하고 옮기면 될듯하다.

삭제의 경우에는.. 글쎄.. 일일이 전체검사를 해야하나? 문제의 상수조건을 보면 수가 그리 크지 않아서 괜찮을지도?

일단 넣어보고 전체검사를 한 다음에 안된다 싶으면 빼는걸로!

 

def valid(structlist, x, y, structure):
    if structure == 0:
        return (x,y,1) in structlist or (x-1,y,1) in structlist or y==0 or (x,y-1,0) in structlist
    else:
        return (x+1,y-1,0) in structlist or (x,y-1,0) in structlist or ((x-1,y,1) in structlist and (x+1,y,1) in structlist) 
        
def all_valid(structlist):
    for x,y,struct in structlist:
        if not valid(structlist,x,y,struct):
            return False
    return True

def solution(n, build_frame):
    
    answer = set()
    
    for x,y,a,b in build_frame:
        if b == 1:
            if valid(answer,x,y,a):
                answer.add((x,y,a))
        else:
            answer.discard((x,y,a))
            if not all_valid(answer):
                answer.add((x,y,a))
                
    answer = list(answer)
    answer.sort()
    
    return answer

 

set로 구현한 이유는 넣고 빼는게 list보다 빠를거같아서. 실제로 리스트에서 빼는 연산은 O(N), set는 O(1)

 

이 문제 첨봤을 땐 좀 많이 어려웠는데 지금 다시 푸니까 꽤 금방푸네? 이게 반복학습의 힘인가?