기둥과 보 설치 (60061번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 기둥과 보 설치 (60061번)

 

난이도 : Lv 3

알고리즘&자료구조 : Implementation (구현)

 

def solution(n, build_frame):
    memo = [[[0, 0] for _ in range(n+1)] for _ in range(n+2)]
    for x, y, a, b in build_frame:
        x += 1
        if b:  # install
            if a:  # beam
                if memo[x][y-1][0] or memo[x+1][y-1][0] or (memo[x-1][y][1] and memo[x+1][y][1]):
                    memo[x][y][1] = 1
            else:  # pillar
                if not y or memo[x][y-1][0] or memo[x-1][y][1] or memo[x][y][1]:
                    memo[x][y][0] = 1
        else:  # delete
            if a:  # beam
                if memo[x-1][y][1] and (memo[x-1][y-1][0] == memo[x][y-1][0] == 0):
                    continue
                if memo[x+1][y][1] and (memo[x+1][y-1][0] == memo[x+2][y-1][0] == 0):
                    continue
                if memo[x][y][0] and (memo[x-1][y][1] == memo[x][y-1][0] == 0):
                    continue
                if memo[x+1][y][0] and (memo[x+1][y][1] == memo[x+1][y-1][0] == 0):
                    continue
                memo[x][y][1] = 0
            else:  # pillar
                if memo[x-1][y+1][1]:
                    if not memo[x-1][y][0] and not (memo[x-2][y+1][1] == memo[x][y+1][1] == 1):
                        continue
                if memo[x][y+1][1]:
                    if not memo[x+1][y][0] and not (memo[x-1][y+1][1] == memo[x+1][y+1][1] == 1):
                        continue           
                if memo[x][y+1][0]:
                    if memo[x-1][y+1][1] == memo[x][y+1][1] == 0:
                        continue
                memo[x][y][0] = 0

    answer = []
    for x in range(1, n+2):
        for y in range(n+1):    
            for i in range(2):
                if memo[x][y][i]:
                    answer.append([x-1, y, i])
    return answer

 

 

2020 KAKAO BLIND RECRUITMENT 기출문제이다.

 

구현 문제 그 자체이다.

 

 

---

 

 

① 보 설치

아래의 3가지 중 하나라도 해당되면, 보 설치가 가능하다.

 

▷ 왼쪽 아래에 기둥이 있다.

 

▷ 오른쪽 아래에 기둥이 있다.

 

▷ 양쪽 모두 보가 있다.

 

 

 

 

② 보 제거

위의 4가지가 모두 해당되면, 보 제거가 가능하다.

 

▷ 왼쪽에 보가 존재한다면, 왼쪽 보의 양 끝 아래 중 적어도 하나의 기둥이 존재해야 한다.

(왼쪽 보가 없으면 상관 없다.)

 

▷ 오른쪽에 보가 존재한다면, 오른쪽 보의 양 끝 아래 중 적어도 하나의 기둥이 존재해야 한다.

(오른쪽 보가 없으면 상관 없다.)

 

▷ 왼쪽에 기둥이 올려져있다면, 왼쪽 보 또는 왼쪽 아래 기둥 중 적어도 하나는 존재해야 한다.

(왼쪽 기둥이 없으면 상관 없다.)

 

▷ 오른쪽에 기둥이 올려져있다면, 오른쪽 보 또는 오른쪽 아래 기둥이 적어도 하나는 존재해야 한다.(오른쪽 기둥이 없으면 상관 없다.)

 

 

 

 

③ 기둥 설치

아래의 4가지 중 하나라도 해당되면, 기둥 설치가 가능하다.

 

▷ 바닥이다.

 

▷ 아래에 기둥이 있다.

 

▷ 왼쪽에 보가 있다.

 

▷ 오른쪽에 보가 있다.

 

 

 

 

④ 기둥 제거

아래의 4가지 중 하나라도 해당되면, 기둥 제거가 가능하다.

 

▷ 왼쪽에 보가 있다면, 왼쪽 보의 왼쪽과 오른쪽에 모두 보가 있거나, 왼쪽 보의 왼쪽 아래에 기둥이 존재해야 한다.

(왼쪽 보가 없으면 상관 없다.)

 

▷ 오른쪽에 보가 있다면, 오른쪽 보의 왼쪽과 오른쪽에 모두 보가 있거나, 오른쪽 보의 오른쪽 아래에 기둥이 존재해야 한다.

(오른쪽 보가 없으면 상관 없다.)

 

▷ 위에 기둥이 있다면, 왼쪽 또는 오른쪽 중 적어도 하나에 보가 존재해야 한다.

(위쪽 기둥이 없으면 상관 없다.)

 

 

---

 

위의 조건들을 그대로 코드로 구현하고,

기둥 또는 보가 존재하는 좌표들을, (x축, y축, 기둥, 보) 순서대로 정렬해서 반환하면 된다.