[2020 KAKAO BLIND RECRUITMENT] 기둥과 보 설치

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

프로그래머스

 

 

1. 틀린 풀이

# 틀린 풀이

def solution(n, build_frame):
    answer = []
    def check(answer):
        for number in answer:
            x, y, a = number
            # 기둥이 설치될 조건
            if a == 0:
                if y == 0 or [x - 1, y, 1] in answer or [x + 1, y, 1] in answer or [x, y - 1, 0] in answer:
                    continue
                return False
            elif a == 1:
                if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or [x - 1, y - 1, 0] in answer or ([x - 1, y, 1] in answer and [x + 1, y, 1] in answer):
                    continue
                else:
                    return False
        return True

        
    
    for frame in build_frame:
        x, y, a, b = frame
        # 삭제
        if b == 1:
            answer.append([x, y, a])
            if check(answer) == False:
                answer.remove([y, x, a])
        # 추가
        else:
            answer.remove([x, y, a])
            if check(answer) == False:
                answer.append([x, y, a])

    return sorted(answer)

????????????????????????????????????????????????? 어째서?

 

일단 whssk 어려웠다... 
해결하지 못해서 처음 아이디어 생각과 설치 조건에 대한 힌트를 받았는데도 3시간이 넘게 걸렸다.
그 외의 코드는 비교적 단순하나 주어진 글을 정말 잘 읽어야 겠다고 생각이 들었다.

본인이 처음 떠오른 아이디어는 n이 100개 까지이기 때문에 2차원 배열에서 O(N^3)까지 해도 문제 없겠구나 라는 것은 알아서 그래프를 생성해서 그래프에 찍어내는 방식으로 해결하려 했지만 스케일이 워낙 커지고 복잡해져서 포기했다.

다른 분들의 도움을 받아 설치 또는 삭제해야할 배열을 answer 배열에 append 또는 remove하고 answer를 check 하는 방식을 채택하였다.

주의해야될 점은 조건문인데,,
check() 함수에서 조건을 보면 보는 좌표점을 기준으로 오른쪽 방향을 보면서 설치되고, 기둥은 죄표점을 기준으로 왼쪽 방향으로 설치된다는 것이다.
무슨말이냐면 (1, 1)에서 보가 설치 가능한지 확인할 때, 설치되면 오른쪽을 바라봐야 한다. 그래서 (1, 0) 기둥 말고 (2, 0)에 기둥이 설치되어있어야 한다. 하지만 (0, 0)은 관련이 없다. 그 이유는 보는 오른쪽 방향을 보고 설치되기 때문이다.
진짜 이거때매 1시간 더 날린 것 같다.

 

2. 정답코드

def check(answer):
    for x, y, a in answer:
        # 기둥이 설치될 조건
        if a == 0:
            # 기둥이 바닥 위치
            if y == 0:
                continue
            # 기둥위에 기둥 위치
            if [x, y - 1, 0] in answer:
                continue
            # 좌 또는 우에 보가 위치
            if [x, y, 1] in answer or [x - 1, y, 1] in answer:
                continue
                
            return False
            
        # 보 설치될 조건
        else:
            # 바닥이 아니어야 함
            if y == 0:
                return False
            # 한쪽 끝에 기둥
            if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer:
                continue
            # 양쪽 끝 보가 위치
            if [x - 1, y, 1] in answer and [x + 1, y, 1] in answer:
                continue
            
            return False
        
    return True

def solution(n, build_frame):
    answer = []    
    
    for frame in build_frame:
        x, y, a, b = frame
        # 삭제
        if b == 1:
            answer.append([x, y, a])
            if check(answer) == False:
                answer.remove([x, y, a])
        # 추가
        else:
            answer.remove([x, y, a])
            if check(answer) == False:
                answer.append([x, y, a])

    return sorted(answer)