구현 | 기둥과 보 설치

Journey log·2021년 6월 17일

[이코테] 알고리즘 공부

목록 보기

15/21

기둥과 보 설치

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

1.1 내 풀이

설치와 삭제 모두 그 근방만 확인함.
테스트 케이스는 돌아가는데 제출하니 런타임오류.
오류 : 설치는 그 주변만 확인하면 되는데, 삭제할 때 그 주변에 고려해야할 경우의 수가 무지 많음. (예: 기둥 삭제하는 부분 틀림) 그래서 차라리 전체적으로 가능한 구조물인지 확인하는게 효율적

def solution(n, build_frame):
    q = []
    
    for x in build_frame:
        a, b = x[0],x[1]
        # 설치
        if x[3] == 1:
            # 기둥
            if (x[2] == 0) and (b==0 or [a,b-1,0] in q or [a,b,1] in q or [a-1,b,1] in q) and b+1 <= n:
                q.append([a,b,0])

            # 보
            if (x[2] == 1) and (b!= 0): # 바닥에는 설치 불가
                # 한쪽 끝이 기둥 위
                if a+1<= n and ([a, b-1, 0] in q or [a+1, b-1, 0] in q) :
                    q.append([a,b,1])

                # 양쪽 끝이 다른 보와 동시에 연결 
                elif a+1 <= n and ([a-1,b,1] in q) and ([a+1, b,1] in q):
                    q.append([a,b,1])

        # 삭제
        elif x[3] == 0:
        
            # 기둥 삭제 
            if x[2] == 0 :
                # 기둥 위에 보와 기둥 모두 없거나
                if [a, b+1, 1] not in q and [a-1,b+1,1] not in q and [a,b+1,1] not in q:
                    q.remove([a,b,0])
                # 기둥 위에 보가 있다면 양옆으로 보 확인
                if ([a,b,1] in q and [a+1,b-1,0] in q) or ([a-1,b,1] in q and [a-1,b-1,0] in q):
                    q.remove([a,b,0]) # 여기부터 
            
            # 보 삭제 (양 옆에 보가 있고 기둥이 안 받치고 있으면 삭제 불가)
            if x[2]==1:
                if not ([a-1,b,1] in q and [a+1,b,1] in q and ([a,b-1,0] not in q or [a+1, b-1, 0] not in q)):
                    q.remove([a,b,1])
            
    q = sorted(q, key = lambda x : (x[0],x[1]))
                    
    return sorted(q)

1.2 책 풀이

'특정 위치에 기둥또는 보를 설치할 수 있는지' 확인할 수 있는건 삭제하는 과정보다 간편. -> 그럼 구조물을 차례대로 설치 혹은 삭제하면서 전체적인 구조물이 가능한지 확인하는 함수를 짜보자.
명령(build_frame)의 개수가 총 1,000개 이하. 전체 명령의 개수를 M이라 하면, 시간복잡도는 O(M^2)으로 해결하는 것이 이상적. 하지만 본 문제에서 시간은 5초로 넉넉해서 O(M^3)의 알고리즘을 이용해도 괜찮음.
각 명령마다 현재 구조물이 가능한지 확인하는 함수 possible를 호출. 만약 가능하지 않다면 그 명령 무시한다.

# 현재 설치된 구조물이 가능한 구조물인지 확인하는 함수
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:
        x,y,stuff,operator = frame
        if operator == 0: # 삭제하는 경우
            answer.remove([x,y,stuff])
            if not possible(answer):
                answer.append([x,y,stuff])
        if operator == 1: # 설치하는 경우
            answer.append([x,y,stuff])
            if not possible(answer):
                answer.remove([x,y,stuff])

    return sorted(answer)