[KAKAO] 기둥과 보 (2020 KAKAO BLIND)

최근 여행을 갔다 온 뒤 다시 코딩을 하니 집중이 잘 되는 것 같다. 최근에 산 IMac도 왔기 때문에 더욱 코딩 할 맛이 나는듯 하다.

알고리즘을 많이 쉰 듯해서 다시 꾸준히 하루 한 문제라도 풀려고 한다.

 

저번에 못 풀었던 카카오 블라인드 문제들을 다시금 봤다. 겁먹지말고 일단 문제에서 하라는 대로 해보자.. 라는 식으로

몇 문제를 풀었는데, 이 문제는 풀릴 듯 하면서도 안 풀리는게 참.. 시간을 많이 잡아 먹었다.

 

조건들이 많이 까다로웠고, 생각을 좀 많이 한 뒤 코딩을 하자.. 느꼈다. 코드를 짜는 시간보다 디버깅의 시간이 더 오래걸렸고

몇 번이나 지우고 다시 썼는지 모르겠다. ㅋㅋ

 

사람들이 생각보다 많이 푼 문제이기도 해서 별 걱정없이 손 댔는데도 많아도 50점(100점 만점) 정도가 나왔던 것 같다.

 

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

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

 

풀이

기둥과 보의 조건

기존 풀이 (59.2점 / 100 점)

1. 기둥을 올릴 때, 보를 깔 때

- 기둥을 올릴 좌표에서 기둥이 올라갈 수 있는지 여부를 판별했다

ex) 기둥을 올릴 때는 해당 기둥 밑에 기둥이 있거나, 보의 한 쪽 끝이거나 .. 등

 

- 보를 올릴 좌표에서 보가 올라갈 수 있는지 여부를 판별했다.

ex) 보를 올릴 때 양쪽 끝이 보이거나, 한 쪽 끝에 기둥이 있는지.. 등

 

2. 기둥을 지울 때, 보를 지울 때

 

위와 마찬가지로 기둥을 지울 때 바로 1. 위의 기둥, 2. 양옆의 보 .... 등 모든 조건들을 생각해 보며 코딩했다.

이런 조건들을 고려하다 보니 코드 량도 많아지고 디버깅도 어려웠다..

 

결론 -> 이렇게 하다 보니 하나라도 고려하지 못하는 조건이 있을 때 분명 오류가 났다.

              어떤 조건을 내가 빠졌는지도 생각하지 못했고 테스트 케이스 또한 몇 개 없다보니 어디서 틀렸는지 알기도 힘들었다.

 

 

정답 풀이 

내가 고려하지 못한 조건들이 없는 것 같았는데 문제를 풀지 못한 것 같아 질문 검색창을 봤다.

질문 검색에서 기둥이나 보를 지울 때 근처의 기둥이나 보를 보면서 맞는지 확인하려 하지말고 전체의 기둥과 보를 한 번 보라는 말이었다.

 

한 마디로 하나를 지우고, 전체 기둥,보 좌표를 보면서 위의 (기둥과 보의 조건)에 해당하는 지 확인하는 것이었다.

하나를 지울 때마다 전체를 탐색해야 하기 때문에 시간이 많이 걸릴듯 하나, 범위를 보니 괜찮겠다 생각했다.

 

이해가 어려우니 다음 예를 보자

 

위의 그림은 기둥이 3개, 보가 3개가 있다.

 

2번째 기둥을 지울 때

1번, 2번 보가 안전한지 검사하는 것 2번 위의 기둥이 있는지 없는 지 등의 예외를 고려하면서 하는 것은 어렵다.

 

따라서 . . .

 

1.  2번기둥을 먼저 지운다. 

 

2. 나머지 1,3번 기둥 1,2,3 보가 위의 <기둥과 보의 조건>에 적합한 지 보는 것이다.

 

3. 하나라도 조건에 맞지 않는다면 다시 기둥을 원상복구 해야 한다. 그렇지 않다면 지운다.

 

 

정답 코드

def solution(n, build_frame):
    answer = []
    PILLAR, BO = 0, 1
    board = [[[0, 0] for i in range(n+1)] for j in range(n+1)]
    
    def upPillar(r, c):
        if checkPillar(r,c):
            board[r][c][PILLAR] = 1
        return
        
    def checkPillar(r,c):
        if r== n or board[r+1][c][PILLAR]:
            return True
        
        if (c-1 >=0 and board[r][c-1][BO]) or board[r][c][BO]:
            return True
        
        return False
        
    def checkBo(r,c):
        if c-1 >= 0 and c+1 <= n:
            if board[r][c-1][BO] and board[r][c+1][BO]:
                return True
        
        if board[r+1][c][PILLAR] or board[r+1][c+1][PILLAR]:
            return True
            
        return False

    def removePillar(r, c):
        board[r][c][PILLAR] = 0
        
        for i in range(n+1):
            for j in range(n+1):
                if board[i][j][BO] and not checkBo(i, j):
                    board[r][c][PILLAR] = 1
                    return
                if board[i][j][PILLAR] and not checkPillar(i,j):
                    board[r][c][PILLAR] = 1
                    return
        return
    
    def addBo(r, c):        
        if checkBo(r,c):
            board[r][c][BO] = 1
        return
        
    def removeBo(r, c):
        
        board[r][c][BO] = 0
        
        for i in range(n+1):
            for j in range(n+1):
                if board[i][j][PILLAR]:
                    if not checkPillar(i, j):
                        board[r][c][BO] = 1
                        return
                if board[i][j][BO]:
                    if not checkBo(i,j):
                        board[r][c][BO] = 1
                        return
    
        return  
    
    for x, y, a, b in build_frame: # a (0: 기둥, 1: 보) b (0: 삭제, 1: 설치)
        c, r = x, n - y
        if a == PILLAR:
            if b == 1: upPillar(r, c)
            else: removePillar(r, c)
        else:
            if b == 1: addBo(r,c)
            else: removeBo(r,c)
    
    for i in range(n+1):
        for j in range(n+1):
            for k in range(2):
                if board[i][j][k] == 1:
                    answer.append([j, n-i, k])
        
    return sorted(answer, key = lambda x: (x[0], x[1], x[2]))