[이코테] 구현 - 기둥과 보 설치

문제 <기둥과 보 설치>

2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다.

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

2차원 벽면은 n x n 크기 정사각 격자 형태이며, 각 격자는 1 x 1 크기입니다.

벽면의 크기 n, 기둥과 보를 설치하거나 삭제하는 작업이 순서대로 담긴 2차원 배열 build_frame이 매개변수로 주어질 때, 모든 명령어를 수행한 후 구조물의 상태를 return 하도록 solution 함수를 완성해주세요.

 

---

제한사항

• n은 5 이상 100 이하인 자연수입니다.
• build_frame의 세로(행) 길이는 1 이상 1,000 이하입니다.
• build_frame의 가로(열) 길이는 4입니다.
• build_frame의 원소는 [x, y, a, b]형태입니다.
  • x, y는 기둥, 보를 설치 또는 삭제할 교차점의 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
  • a는 설치 또는 삭제할 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
  • b는 구조물을 설치할 지, 혹은 삭제할 지를 나타내며 0은 삭제, 1은 설치를 나타냅니다.
  • 벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.
  • 바닥에 보를 설치 하는 경우는 없습니다.
• 구조물은 교차점 좌표를 기준으로 보는 오른쪽, 기둥은 위쪽 방향으로 설치 또는 삭제합니다.
• 구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.
• 최종 구조물의 상태는 아래 규칙에 맞춰 return 해주세요.
  • return 하는 배열은 가로(열) 길이가 3인 2차원 배열로, 각 구조물의 좌표를 담고있어야 합니다.
  • return 하는 배열의 원소는 [x, y, a] 형식입니다.
  • x, y는 기둥, 보의 교차점 좌표이며, [가로 좌표, 세로 좌표] 형태입니다.
  • 기둥, 보는 교차점 좌표를 기준으로 오른쪽, 또는 위쪽 방향으로 설치되어 있음을 나타냅니다.
  • a는 구조물의 종류를 나타내며, 0은 기둥, 1은 보를 나타냅니다.
  • return 하는 배열은 x좌표 기준으로 오름차순 정렬하며, x좌표가 같을 경우 y좌표 기준으로 오름차순 정렬해주세요.
  • x, y좌표가 모두 같은 경우 기둥이 보보다 앞에 오면 됩니다.

---

입출력

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

• n = 5
• build_frame = [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]]
• result = [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]]

• n = 5
• build_frame = [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]]
• result = [[0,0,0],[0,1,1],[1,1,1],[2,1,1],[3,1,1],[4,0,0]]

---

풀이

• 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
• 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.

다음 두 가지 조건을 중점으로 문제를 해결하고자 하였다.

처음에는, 설치와 삭제 시 생각해야 하는 조건이 다르다고 생각했다.

벽면을 벗어나게 기둥, 보를 설치하는 경우는 없습니다.

바닥에 보를 설치 하는 경우는 없습니다.

이 두 가지 조건을 보고 벽면을 벗어나게 기둥과 보를 설치하거나, 바닥에 보를 설치하는 경우도 직접 설치에서 제외시켜 주어야 겠다고 생각했고,

구조물이 겹치도록 설치하는 경우와, 없는 구조물을 삭제하는 경우는 입력으로 주어지지 않습니다.

이 조건을 보고 설치할 때는 벽면과 벗어나는지 체크를 해주고, 삭제할 때는 해당 구조물을 삭제할 때 특정 조건을 체크할 필요가 없다고 생각해 설치와 삭제를 따로 분리해 문제를 풀었다.

따로 함수를 만들어 문제를 해결하지 않아 가독성이 떨어졌지만, 당시에는 문제를 해결하는 데 중점을 두었다.

def solution(n, build_frame):
    answer = []   # [기둥, 보의 교차점 좌표(가로, 세로), 구조물(기둥 : 0, 보 : 1)]
    for i in range(len(build_frame)):
        if build_frame[i][3] == 1:
            if build_frame[i][2] == 0 and not (build_frame[i][0]<0 or build_frame[i][0]>n or build_frame[i][1]<0 or build_frame[i][1]>=n):
                if build_frame[i][1] == 0 or [build_frame[i][0], build_frame[i][1], 1] in answer or [build_frame[i][0]-1, build_frame[i][1], 1] in answer or [build_frame[i][0], build_frame[i][1]-1, 0] in answer:
                    answer.append([build_frame[i][0], build_frame[i][1], 0])
            elif build_frame[i][2] == 1 and not (build_frame[i][0]<0 or build_frame[i][0]>=n or build_frame[i][1]<0 or build_frame[i][1]>n):
                if build_frame[i][1] != 0 and [build_frame[i][0], build_frame[i][1]-1, 0] in answer or [build_frame[i][0]+1, build_frame[i][1]-1, 0] in answer or ([build_frame[i][0]-1,build_frame[i][1],1] in answer and [build_frame[i][0]+1,build_frame[i][1],1] in answer):
                    answer.append([build_frame[i][0], build_frame[i][1], 1])
        elif build_frame[i][3] == 0:
            answer.remove([build_frame[i][0], build_frame[i][1], build_frame[i][2]])
            remove = True
            for i in range(len(answer)):
                if answer[i][2] == 0:
                    if not (answer[i][1] == 0 or [answer[i][0], answer[i][1], 1] in answer or [answer[i][0] + 1, answer[i][1], 1] in answer or [answer[i][0], answer[i][1] - 1, 1] in answer):
                        remove = False
                elif answer[i][2] == 1:
                    if not ([answer[i][0], answer[i][1]-1, 0] in answer or [answer[i][0]+1, answer[i][1]-1, 0] in answer or ([answer[i][0]-1,answer[i][1],1] in answer and [answer[i][0]+1,answer[i][1],1] in answer)):
                        remove = False
            if not remove:
                answer.append([build_frame[i][0], build_frame[i][1], build_frame[i][2]])
    answer.sort(key=lambda x: (x[0],x[1],x[2]))
    return answer

나와있는 두 가지 테스트 케이스는 통과했지만, 다른 케이스들에서 런타임 에러가 발생하는 것을 확인할 수 있었다.
확실히 가독성이 떨어지게 코드를 작성하니 이후에 코드를 수정할 때 놓친 부분을 찾기 어려웠다.

그래서 조건을 다시한번 확인해보고 테스트 케이스를 보니, 설치할 때 벽면에 벗어나는지 여부를 신경쓰지 않아도 될 것 같았다.

설치와 삭제를 한 번에 함수로 해결할 수 있겠다!
구조물을 설치 혹은 삭제한 후 그 구조물이 안정적인지 여부를 확인하는 함수를 만들어보자

def possible(answer):   # 현재 구조물이 가능한지 여부 반환하는 함수
    poss = True
    for x, y, z in answer:
        if z == 0:      # 기둥일 때
            if not (y == 0 or [x-1, y, 1] in answer or [x, y, 1] in answer or [x, y-1, 0] in answer):   # 기둥일 때의 조건에 부합하지 않으면
                return False
        else:           # 보일 때
            if not ([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)):    # 보일 때의 조건에 부합하지 않으면
                return False
    return True

def solution(n, build_frame):
    answer = []   # [기둥, 보의 교차점 좌표(가로, 세로), 구조물(기둥 : 0, 보 : 1)]
    for x, y, z, w in build_frame:   # 설치하거나 삭제하는 작업
        if w == 1:      # 설치
            answer.append([x, y, z])    # 먼저 설치하기
            if not possible(answer):    # 설치한 후의 구조물이 가능하지 않다면
                del answer[len(answer)-1]   # 설치 취소
        else:       # 삭제
            answer.remove([x, y, z])    # 먼저 삭제하기
            if not possible(answer):        # 삭제한 후의 구조물이 가능하지 않다면
                answer.append([x, y, z])       # 삭제 취소
    answer.sort(key=lambda x: (x[0], x[1], x[2]))   # x, y 좌표, 기둥->보 순으로 오름차순 정렬
    return answer

23개의 모든 테스트를 통과하였다.

• build_frame 리스트 안에 있는 원소들을 x, y, z, w로 특정하니 코드의 가독성이 높아졌다.
• 함수를 설정하여 설치와 삭제에서 동일한 코드를 사용하니 가독성이 높아지고, 코드 리펙토링을 하기가 보다 더 쉬웠다.
• 이 문제의 요점은 설치와 삭제를 하나로 묶어서 설치 혹은 삭제를 했을 때 구조물이 안정적으로 유지 되는지를 확인하는 것이었다.
• 처음에는 설치와 삭제의 작업을 따로 생각하여 함수를 만들지 않아 코드가 복잡했지만, 문제의 요점을 파악하니 어렵지 않은 문제였다.

---

구현 문제는 문제를 풀기 전에 조건을 정확히 파악하는 습관을 다시한번 가져야겠다!

반복되는 코드가 있을 때에는 함수를 이용하고, 처음 문제를 풀 때 코드의 가독성을 높이기 위한 방법을 고민해보자!

 

 

프로그래머스