문제링크
기둥과 보를 설치 및 제거가 가능한지 확인하면서 진행후 결과를 반환하는 것
기둥은
세 가지 경우에서 살펴보고 설치가 가능하다.
보는
두 가지 경우를 보고 설치할 수 있다.
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) # 정렬된 결과를 반환
해당 문서는 '이것이 코딩 테스트다 - 나동빈 저'를 공부하며 스스로 정리한 문서입니다.