프로그래머스 2020 KAKAO BLIND RECRUITMENT 구현 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.

문제

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

[나의 풀이]

⌛ 시간초과 (9.6/100점)

def solution(n, build_frame):
    answer = []
    
    wall = [[-1 for j in range(n+1)] for i in range(n+1)] # -1:빈공간,0:기둥,1:보 
    
    for frame in build_frame:
        x, y, beam, install = frame
        
        if install: # 설치
            now = wall[x][y]
            
            if not beam: # 기둥
                        
                check_l = wall[x-1][y]
                check_d = wall[x][y-1]
                
                if (y==0 and now==-1) or (check_d==0)or(check_l==1):
                    wall[x][y] = 0
                    print(x,y,"기둥 설치!")

            else: # 보
                check_d = wall[x][y-1]
                check_r_d = wall[x+1][y-1]
                check_l = wall[x-1][y]
                check_r = wall[x+1][y]
                
                if (now==0 or check_r==0) or (check_l==1 and check_r==1):
                    wall[x][y] = 1
                    print(x,y,"보 설치!")
                    
        else:
            now = wall[x][y]
            if not beam: # 기둥
                check_u = wall[x][y]
                check_u_l = wall[x-1][y+1]
                check_u_r = wall[x+1][y+1]
                
                if not (check_u==1 and check_u_l==1 and check_u_r==1):
                    wall[x][y] = -1
                    # print(x,y,"기둥 제거!")
                    
            else: # 보
                check_l = wall[x-1][y]
                check_r = wall[x+1][y]
                
                if not (now==1 and check_l==1 and check_r==1):
                    wall[x][y] = -1
                    # print(x,y,"보 제거!")
                    
                    
    # print(wall)
    
    for i in range(n+1):
        for j in range(n+1):
            v = wall[i][j]
            if v != -1:
                answer.append([i,j,v])
        
    answer.sort()
    # print(answer)
    return answer

주어지 n차원 평면과 [[x좌표,y좌표,기둥or보,설치or삭제], ...] 입력값이 주어지고 기둥과 보의 설치 및 삭제 규칙에 따라 완성되는 건축물을 반환하는 문제입니다.🐈🐈🐈

wall이라고 하는 2차원 평면을 -1로 모두 초기화하고

위 규칙에 따라서 조건을 정리한 뒤

# 기둥 설치
# 1) 바닥 위
# 2) 보의 한쪽 끝
# 3) 기둥 위

# 보 설치
# 1) 한쪽 끝이 기둥 위
# 2) 양쪽 끝이 다른 보

### 삭제

# 기둥&보
# 삭제 후에도 설치 규칙을 만족

이를 if-else문으로 구현하려하였으나 '삭제' 가능한 조건들을 모두 고려하는 것이 까다로워 시간을 초과하였고 이에 따라 다른 풀이를 참고하였습니다.

[다른 사람의 풀이1]

def solution(n, build_frame):
    def is_valid_structure(x, y, a, result):
        if a == 0: # 보
            if y == 0 or [x, y-1, 0] in result or [x, y, 1] in result or [x-1, y, 1] in result:
                return True
        else: # 기둥
            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):
                return True
        return False

    result = []
    for x, y, a, b in build_frame:
        if b == 1: # 건물 생성
            if is_valid_structure(x, y, a, result):
                result.append([x, y, a])
        else: # 건물 제거
            result.remove([x, y, a])
            for i in result:
                xpos, ypos, stru = i
                if not is_valid_structure(xpos, ypos, stru, result):
                    result.append([x, y, a])
                    break

    answer = sorted(result)
    return answer

'나의 풀이'와 같이 설치,삭제할 때마다 2차원 평면을 갱신하는 것이 아닌 is_valid_strcture()라는 하나의 함수로 규칙에 적합하지 판단하는 방식이였습니다.🕊️🕊️🕊️

건물을 생성할 때 기둥 or 보를 result에 추가한 뒤, 설치가 불가능한지 True or False를 반환하여 판단합니다.

또 삭제할 때는 기둥 or 보를 result에서 제거한 뒤, 삭제가 불가능할 때의 True or False 반환하는 방식입니다.

실제 2차원 평면을 만들어 갱신하지 않은점, 하나의 검증 함수로 설치,삭제를 모두 구현할 수 있다는 점이 포인트였습니다.

[다른 사람의 풀이2]

def check_build(answer):
    for x, y, a in answer:
        # 기둥인 경우
        if a == 0:
            # 좌표가 바닥에 해당 x
            # 좌표 아래에 기둥이 존재 x
            # 보의 한 쪽 위 x
            if (y != 0 and
                [x, y - 1, 0] not in answer and
                [x - 1, y, 1] not in answer and
                [x, y, 1] not in answer):
                return False
        # 보인 경우
        else:
            # 아래애 기둥 존재 x
            # 양쪽에 보 존재 x
            if ([x, y - 1, 0] not in answer and
                [x + 1, y - 1, 0] not in answer and
                ([x - 1, y, 1] not in answer or
                 [x + 1, y, 1] not in answer)):
                return False
    return True
 
def solution(n, build_frame):
    answer = []
    for x, y, a, b in build_frame:
        # 삭제라면
        if b == 0:
            answer.remove([x, y, a])
            # 삭제 후, check가 통과되지 못한다면, 재설치
            if not check_build(answer):
                answer.append([x, y, a])
        # 설치라면
        elif b == 1:
            answer.append([x, y , a])
            # 설치 후, check가 통과되지 못한다면, 삭제처리
            if not check_build(answer):
                answer.remove([x, y, a])
 
    answer.sort(key= lambda x : (x[0], x[1], x[2]))
    return answer

'다른 사람의 풀이1'과 같이 설치 및 삭제를 진행한 뒤, 이것이 가능한지 판단하는 함수로 판별하는 방식입니다.🐇🐇🐇

구현 문제같은 경우 자신있었지만 해당 문제의 경우 하드코딩으로 구현하기 까다로운 측면과 설치 및 삭제에 대해 하나의 판별 함수를 만들어 해결한 아이디어를 생각해내기 어려웠습니다.

다음에 다시 도전해보겠습니다. 감사합니다.