[프로그래머스 - 카카오] 기둥과 보

koyo·2020년 9월 27일
0

프로그래머스

목록 보기
1/3
post-thumbnail

문제

문제링크
기둥과 보를 설치 및 제거가 가능한지 확인하면서 진행후 결과를 반환하는 것
기둥은

  1. 아래가 땅인가?
  2. 보의 위에 존재하는가?
  3. 아래에 기둥이 있는가?

세 가지 경우에서 살펴보고 설치가 가능하다.

보는

  1. 아래에 기둥이 있는가?
  2. 양 끝에 보가 이어지는가?

두 가지 경우를 보고 설치할 수 있다.

문제 푸는 중 문제점

frame의 수가 최대 1000인데, 이 경우 시간복잡도 O(n^3) 까지 괜찮다. 하지만, 다 살펴보면 문제가 있을 것 같아 시도하지 않은 것이 문제였다. 그래서 삭제하고 영향 받을 수 있는 모든 건축물에 접근해서 여부를 따졌는데, 그걸로는 해결 안되는 것 같았다.

또한 보를 설치 및 제거시 기둥에 이어져있는 보를 체크하였는데, 앞에 연산을 통해 보장하는 점을 놓친 것 같다.

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

# 현재 설치된 구조물이 '가능한' 구조물인지 확인하는 함수
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 # 아니라면 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 # 아니라면 False
    return True

def solution(n, build_frame):
    answer = []
    for frame in build_frame: # 작업(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) # 정렬된 결과를 반환

해당 문서는 '이것이 코딩 테스트다 - 나동빈 저'를 공부하며 스스로 정리한 문서입니다.

profile
클라우드 개발자가 될 코요입니다.

0개의 댓글