[Algorithm] 기둥과 보 설치

이 문제는 2020 카카오 신입 공채 코딩테스트에 출제되었던 문제이다. 아래의 링크를 참고하자.

 

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

프로그래머스

 

이 문제는 전형적인 시뮬레이션 문제이다. 문제에서 제시한 구체적인 처리 과정을 프로그램 상에서 차례대로 수행하여 결과를 도출하면 된다. 이 문제의 전체 명령의 개수는 1,000개이하이며 제한 시간은 5초로 넉넉한 편이다. 따라서 O(M^3)의 시간복잡도 알고리즘을 사용해도 문제를 해결할 수 있다. 가장 간단한 방법은, 설치 및 삭제 연산을 요구할 때마다 일일이 '전체 구조물을 확인하며' 규칙을 확인하는 것이다.

 

우선 possible 함수를 만들어 현재 구조물이 설치 조건에 부합하는지 확인하고, 부합하지 않는다면 현재의 연산을 무시하도록 한다. 

 

그리고 구조물의 상태를 반환하는 solution 함수를 작성한다. 

 

# 기둥과 보 설치

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
def possible(answer):
    for x, y, stuff in answer:
        if stuff == 0: # 기둥
            # '바닥 위' 혹은 '보의 한쪽 끝부분 위' 혹은 '다른 기둥 위'라면 정상
            if y == 0 or [x - 1, y, 1] in answer or [x, y, 1] in answer or [x, y - 1, 0] in answer:
                continue
            return False
        elif stuff == 1: # 보
            # '한쪽 끝부분이 기둥 위' 혹은 '양쪽 끝부분이 다른 보와 동시에 연결'이라면 정상
            if [x, 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
            return False
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame: # 작업의 개수는 최대 1,000개
        x, y, stuff, operate = frame
        if operate == 0: # 삭제하는 경우
            answer.remove([x, y, stuff]) #일단 삭제를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.append([x, y, stuff]) # 가능한 구조물이 아니라면 다시 설치
        if operate == 1: # 설치하는 경우
            answer.append([x, y, stuff]) # 일단 설치를 해본 뒤에
            if not possible(answer): # 가능한 구조물인지 확인
                answer.remove([x, y, stuff]) # 가능한 구조물이 아니라면 다시 제거

    return sorted(answer) # 정렬된 결과를 반환