[이코테] 구현_기둥과 보 설치 (python)

문제

나의 풀이

: 이건 검색해서 힌트를 얻고 다시 풀었다 ㅠ

1. deque 이용(근데 for로 돌려도 될듯..) : 성공

from collections import deque

def is_satisfy(answer): # 설치/삭제 조건을 충족하는가?
    for x, y, a in answer: # 설치/삭제에 따라 now가 달라짐
        if a == 0: # 기둥인 경우
            # 바닥 위 or 보의 한쪽 끝 부분 위 or 기둥 위 
            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
            
        else: # 보인 경우
            # 한쪽 끝 부분이 기둥 위 or 양쪽 끝 부분이 다른 보와 동시에 연결
            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):
    now, answer = [], [] # 현재 단계, 정답 list 초기화
    build_frame = deque(build_frame) # deque
        
    while build_frame: # build_frame가 존재하는한
        now = build_frame.popleft() # 현재 단계를 뽑아내고
        if now[3] == 0: # 삭제(now: 가로, 세로, 구조물, 설치/삭제)
            answer.remove(now[:3]) # answer에서 삭제
            if not is_satisfy(answer): # 조건을 충족하지 못하면
                answer.append(now[:3]) # 삭제한거 취소
                
        else: # 설치
            answer.append(now[:3]) # answer에 추가(설치)
            if not is_satisfy(answer): # 조건을 충족하지 못하면
                answer.remove(now[:3]) # 추가(설치)한거 취소
                
    return sorted(answer) # 정렬된 answer 값 반환

• IndexError: list index out of range

: 지쳤는지.. 풀 힘이 안난다 ㅠ

1. 지침
2. 어려운 문제는 아닌데, 조건을 일일히 하려니까..지저분함
3. 지저분 지저분 지저분 ㅠ
   -> 결국 구글링

• def is_satisfy(now_list, answer): for x, y, a, b in now_list:
  : 처음에는 이렇게 했더니.. now_list에 now가 들어갈 땐 인자가 4개지만 answer가 들어갈 땐 인자가 3개가 되어서, 제대로 unpacking 되지 않았다!

그래서..

• def is_satisfy(answer): for x, y, a in answer: 로 바꾸고, 설치 조건을 아래와 같이 바꿨다

else: # 설치
	answer.append(now[:3]) # answer에 추가(설치)
	if not is_satisfy(answer): # 조건을 충족하지 못하면
		answer.remove(now[:3])

: 사실 now만 조건 검사하면 되는 일이지만, 코드를 짧게 짜려다보니 이렇게.. 근데 아마 시간 복잡도는 늘었을듯?

• 진짜로 시간 복잡도가 어마무시하다ㅠ
  : 테스트 15 〉 통과 (2278.72ms, 10.4MB)
  : 작성하다보니 while로 하긴 했지만.. for로 하면 좀 더 빠르겠지?

2. 성공

# 기둥과 보
# x, y, a, b : x좌표, y좌표, 구조물(0: 기둥, 1: 보), 설치 유무(0: 삭제, 1: 설치)
def is_ok(result): # 지금 상태, 괜찮을까?
    for x, y, a in result:
        if a: # 보일 때
            if [x, y - 1, 0] in result or [x + 1, y - 1, 0] in result or ([x - 1, y, 1] in result and [x + 1, y, 1] in result):
                continue
            return False
        else: # 기둥일 때
            if not y or [x, y, 1] in result or [x - 1, y, 1] in result or [x, y - 1, 0] in result:
                continue
            return False
    return True
    
def solution(n, build_frame):
    result = []
    for build in build_frame: # build_frame을 하나씩 살펴보며
        if build[3]: # 설치
            result.append(build[:3]) # x,y,a(구조물) 추가
            if not is_ok(result): # 지금 상태 안 괜찮다면
                result.remove(build[:3]) # 설치한거 다시 삭제
        else: # 삭제
            result.remove(build[:3]) # x,y,a(구조물) 제거
            if not is_ok(result): # 지금 상태 안 괜찮다면
                result.append(build[:3]) # 삭제한거 다시 설치
                
    return sorted(result) # 정렬해서 반환

• def is_ok(result)에서 [x, 0, a] in result 일때는 실패하고, not y 일 때는 성공함.. 왜??
• if문에서 or 여러개를 조심하자! (더보기)
• 시간 복잡도
  : 테스트 15 〉 통과 (3071.09ms, 10.6MB)
  • deque가 더 빠른거 같음 ㅠ