본문 바로가기

알고리즘 삽질장

[이코테] 구현 - 기둥과 보 설치

반응형

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 


문제설명

하단의 링크를 참조하자.

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

 

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

5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[

programmers.co.kr

사고과정

  • 일반적인 구현문제처럼 2차원 리스트 좌표 평면에서 값을 하나하나씩 갱신하는 것으로 풀으려고 했으나 너무 로직이 복잡해져 다 커버하지 못하고 풀지 못했다.. 
  • 풀이를 보니 2차원 리스트를 쓰긴 썼지만 좌표평면을 사용한 게 아니라 주어지는 정보를 리스트에 담아서 처리하는 방법으로 했다. 구현 문제를 이렇게도 푸는구나를 느끼면서 매우 충격이었다.. 먼저 연산(삭제/설치)를 기준으로 나누어서 기둥/보 설치할 때 가능여부 삭제할 때 가능여부를 탐색하면서 풀었다. 시간 복잡도가 $O(M^3)$이긴 했지만 주어진 시간 제한이 5초이고 주어진 범위가 1000이하히기 때문에 넉넉하게 해결할 수 있다고 한다..
  • 그리고 놓치지 말아야 할 점은.. 좌표평면을 사용하지 않았기 때문에 주어지는 x, y 좌표는 문제에서 입출력 예시로 정해준 x, y 축을 그대로 따라 간다. 즉, 파이썬으로 2차원 리스트로 만들어줄때 좌표랑 문제에서 주어지는 좌표랑 공간 기준이 동일하지 않음을 잊지말자!

풀이(스스로 못 푼 풀이)

def check_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:
        x, y, stuff, operate = frame
        # 설치인 경우
        if operate == 1:
            answer.append([x, y, stuff])
            if not check_possible(answer): # 설치 후 불가능 경우라면
                answer.remove([x, y, stuff])
        # 삭제인 경우
        if operate == 0:
            answer.remove([x, y, stuff])
            if not check_possible(answer): # 삭제 후 불가능 경우라면
                answer.append([x, y, stuff])
    
    return sorted(answer)
반응형