Level 3 기둥과 보 설치 <2020 KAKAO BLIND RECRUITMENT> Python 3

https://programmers.co.kr/learn/courses/30/lessons/60061?language=python3 

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

 

최종 코드

• Github -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level3_기둥과보설치.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

def check_possible(answer):
    for x, y, a in answer:
        #기둥
        if a == 0:
            if (y == 0) or ([x, y, 1] in answer) or ([x-1, y, 1] in answer) or ([x, y-1, 0] in answer): continue
            return False
        #보
        else:
            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 x, y, a, b in build_frame:
        item = [x, y, a]
        #설치
        if b == 1:
            answer.append(item)
            if not check_possible(answer):
                answer.remove(item)
        #삭제
        elif item in answer:
            answer.remove(item)
            if not check_possible(answer):
                answer.append(item)
                
    return sorted(answer, key = lambda x:(x[0], x[1], x[2]))

---

풀이 과정

 

def check_possible(answer):
	#기둥과 보가 올바르게 설치되었는지를 판단한다
    for x, y, a in answer:
        #기둥인 경우,
        if a == 0:
        	#바닥 위에 있거나, 보의 한 쪽 끝 부분의 위에 있거나, 다른 기둥 위에 있는 경우, 올바르게 설치된 기둥이다
            if (y == 0) or ([x, y, 1] in answer) or ([x-1, y, 1] in answer) or ([x, y-1, 0] in answer): continue
            
            #아닌 경우, 규칙에 어긋나므로 False를 리턴한다
            return False
            
        #보인 경우,
        else:
        	#한 쪽 끝 부분이 기둥 위이거나, 양쪽 끝부분이 다른 보와 연결되어 있는 경우, 올바르게 설치된 보이다
            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
            
            #아닌 경우, 규칙에 어긋나므로 False를 리턴한다
            return False
        
    return True
    
def solution(n, build_frame):
    answer = []
    
    for x, y, a, b in build_frame:
        item = [x, y, a]
        
        #item을 설치하는 경우,
        if b == 1:
        	#answer에 item을 추가한다
            answer.append(item)
            
            #item을 추가한 후, 규칙에 어긋나지 않는지 판단한다
            #규칙에 어긋나는 경우, 해당 아이템을 answer에서 삭제하여 최종적으로 추가 명령을 무시한다
            if not check_possible(answer):
                answer.pop()
                
        #item을 삭제하는 경우,
        elif item in answer:
        	#answer에서 item을 삭제한다
            answer.remove(item)
            
            #item을 삭제한 후, 규칙에 어긋나지 않는지 판단한다
            #규칙에 어긋나는 경우, 해당 아이템을 다시 answer에 추가하여 최종적으로 삭제 명령을 무시한다
            if not check_possible(answer):
                answer.append(item)
                
    return sorted(answer, key = lambda x:(x[0], x[1], x[2]))
    
#시간복잡도 = O(n^4), 공간복잡도 = O(n)

---

참고

• 1. 문자열 압축 ->2021.09.05 - [코테 노트/프로그래머스] - Level 2 문자열 압축 <2020 KAKAO BLIND RECRUITMENT > Python 3
• 2. 괄호 변환 ->2021.09.05 - [코테 노트/프로그래머스] - Level 2 괄호 변환 <2020 KAKAO BLIND RECRUITMENT> Python 3
• 3. 자물쇠와 열쇠 ->2021.09.05 - [코테 노트/프로그래머스] - Level 3 자물쇠와 열쇠 <2020 KAKAO BLIND RECRUITMENT> Python 3

• 4. 가사 검색 -> 2021.09.06 - [코테 노트/프로그래머스] - Level 4 가사 검색 <2020 KAKAO BLIND RECRUITMENT> Python 3

• 6. 외벽 점검 -> 2022.04.07 - [코테 노트/프로그래머스] - Level 3 외벽 점검 <2020 KAKAO BLIND RECRUITMENT> Python 3

Level 3 외벽 점검 <2020 KAKAO BLIND RECRUITMENT> Python 3

• 7. 블록 이동하기 ->