구현 알고리즘 : 기둥과 보 설치 - 파이썬 (python)

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

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

 

* 아이디어1 → 구현 실패

(1) 2n 크기의 배열을 0으로 초기화하여 새로 생성한다.

(2) 첫 번째 칸과 마지막 칸은 한 칸을 차지하며 그 외 나머지 칸은 양쪽 연결 여부를 표시하기 위해 2칸을 차지한다.

ar = [[0 for i in range(2 * n)] for j in range(2 * n)]

 

(3) build_frame 배열에서 x좌표와 y좌표 값을 얻어내고 x와 y의 값이 0이거나 n인 경우,

기둥인지 보인지의 경우, 설치인지 제거인지의 경우를 고려하여 해당하는 경우 ar의 값을 1로 변경한다.

x나 y 좌표의 값이 0인 경우 2*n-1의 값이 -1이 되므로 0으로 바꾸어주는 과정이 필요하고

x나 y 좌표의 값이 n인 경우에는 2*n의 경우 인덱스를 벗어나므로 2*n-1로 바꿔주는 과정이 필요하다.

즉, 위의 경우 기둥인 경우 기준 ar[2 * x - 1][2 * y - 1] = 1와 ar[2 * x - 1][2 * y] = 1 중 하나만 실행 ...

실행하기 전, 설치나 제거가 가능한지 여부 체크

엄청 복잡해진다

 

for i in range(len(build_frame)):
         # x좌표, y좌표
         x = build_frame[i][0]
         y = build_frame[i][1]
         
         if x != 0 and y != 0:
         
         # 기둥인 경우
             if build_frame[i][2] == 0:
                 ar[2 * x - 1][2 * y - 1] = 1
                 ar[2 * x - 1][2 * y] = 1

             # 보인 경우
             else:
                 ar[2 * x - 1][2 * y - 1] = 1
                 ar[2 * x][2 * y - 1] = 1

 

* 아이디어2 → 교재 풀이

(1) 가능한 구조물인지 확인하는 함수 possible

- 기둥은 바닥 위에 있거나 보의 한쪽 끝부분 위에 있거나, 또는 다른 기둥 위에 있어야 한다.

        ① 기둥이 바닥 위에 있는 경우: y가 0인 경우

        ② 보의 한쪽 끝부분 위에 있는 경우: [x-1, y, 1] 또는 [x, y, 1] 이 존재하는 경우

        ③ 다른 기둥 위에 있는 경우:  [x, y-1, 0] 가 존재하는 경우

 

- 보는 한쪽 끝부분이 기둥 위에 있거나, 또는 양쪽 끝부분이 다른 보와 동시에 연결되어 있어야 한다.

        ① 한 쪽 끝부분이 기둥 위에 있는 경우: [x, y-1, 0] 또는 [x+1, y-1, 0] 이 존재하는 경우

        ② 양쪽 끝부분이 다른 보와 동시에 연결되어 있는 경우: [x-1, y, 1] 과 [x+1, y, 1] 이 존재하는 경우

 

# 가능한 구조물인지 체크
def possible(answer):
    for x, y, stuff in answer:
        # 기둥인 경우
        if stuff == 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

        # 보인 경우
        elif stuff == 1:
            # 한쪽 끝부분이 기둥 위 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

 

(2) 가능한 구조물인지 확인 후 삭제 또는 설치 수행한다.

def solution(n, build_frame):
    answer = []

    for frame in build_frame:
        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)

 

 

 

https://github.com/501501/codingTest/blob/master/%EA%B5%AC%ED%98%84/A12.py

GitHub - 501501/codingTest: 이것이 취업을 위한 코딩테스트다 with 파이썬