[코딩테스트] 프로그래머스 - 기둥과 보 (2020 Kakao) in Python

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성!

 

 

더 상세한 설명↓

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

 

문제풀이는 프로그래머스의 강의를 바탕으로 작성하였습니다.

 

풀이

- 요구사항이 아주 자세하게 문제에 적혀 있다.

- 요구사항을 하나 하나 따라하면 되는, "시뮬레이션 - Simulation" 문제로 정의될 수 있다 한다.

- 시뮬레이션 문제는 보통 시간복잡도에 있어서 널널하게 주어진다고 한다.

~> 이번 문제 또한 O(N^3)으로도 (배열 활용), O(N^2)으로도 (Set와 Tuple활용) 가능하다.

 

리마인더

- 요구사항 및 확인해야 하는 것이 복잡하고 많을 때는, 구현 실수를 줄이기 위해 메소드를 따로 만들어주는 것이 좋다.

 

- 이 문제에서도, 기둥/보의 삭제/설치 과정을 수행한 후, 남아있는 구조물이 '가능한' 구조물인 지 확인하는 메소드를 따로 만들어주면 용이하다.

~> 각 삭제/설치 과정을 수행 후, 남아있는 구조물이 가능하면 그대로 둠

~> 가능하지 않으면, 방금 했던 과정 취소

 

 

구현

def possible(answer):
    for x, y, stuff in answer:
        # if column
        if stuff == 0:
            #possible if it stands on the bottom, or on an end of a beam
            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
        # if beam
        elif stuff == 1:
            #possible if it sits on a column, or its both ends are connected to other beams
            if (x+1,y-1,0) in answer or (x,y-1,0) in answer or  ((x-1,y,1) in answer and (x+1, y, 1) in answer):
                continue
            return False
    return True


# solution
def solution(n,build_frames):
    answer = set() # set and tuples instead of arrays for faster removal of elements
    for frame in build_frames:
        x,y,stuff,action = frame
        # if removal
        if action == 0:
            answer.remove((x,y,stuff))
            if not possible(answer):
                answer.add((x,y,stuff))
        # if create
        else:
            answer.add((x, y, stuff))
            if not possible(answer):
                answer.remove((x, y, stuff))

    return sorted(answer)

 

- answers = []로, [x, y, stuff]로 배열을 사용해도 풀리지만 시간 복잡도는 위에서 말했듯, O(N^3)이 된다!

 

- Simulation문제는 얼마나 정확히, 그리고 효율적으로 요구사항을 구현할 수 있는 지에

달렸다는 거 다시 기억합시다..