[프로그래머스][KAKAO_BLIND][2020] 기둥과 보 설치

프로그래머스 코딩테스트 고득점 Kit의 문제입니다.

https://programmers.co.kr/learn/challenges?tab=algorithm_practice_kit

코딩테스트 연습

 

문제

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

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

 

내가 작성한 코드

# 아래 다른 분의 코드를 참고하여 작성
def satisfied(construct, n):
    for r, c, a in construct:
        # 기둥
        if a == 0:
            # 1. 바닥일 때
            if r == n-1:
                continue
            # 2. 기둥 위 일때
            if (r+1, c, 0) in construct:
                continue
            # 3. 보 위 일 때
            if (r, c-1, 1) in construct or (r, c, 1) in construct:
                continue
            return False
        # 보
        else:
            # 1. 기둥 위 일 때
            if (r+1, c, 0) in construct or (r+1, c+1, 0) in construct:
                continue
            # 2. 보와 보를 연결할 때
            if (r, c-1, 1) in construct and (r, c+1, 1) in construct:
                continue
            return False
    return True


def add(construct, crnt, n):
    construct.append(crnt)
    if not satisfied(construct, n):
        construct.pop()
        return False
    return True

def remove(construct, crnt, n):
    construct.remove(crnt)
    if not satisfied(construct, n):
        construct.append(crnt)
        return False
    return True

def solution(n, build_frame):
    answer = []
    construct = []
    # 좌표로 볼 때 n+1개
    n += 1

    for const in build_frame:
        # (x,y)에 a(0:기둥,1:보)를 b(0:삭제,1:설치)
        # 좌표를 편하게 사용하기위해 (n-y-1, x)를 사용
        x, y, a, b = const
        if b == 0:
            if remove(construct, (n-y-1, x, a), n):
                answer.remove([x,y,a])
        else:
            if add(construct, (n-y-1, x, a), n):
                answer.append([x,y,a])

    return sorted(answer)

• 추가/제거된 건축물(기둥/보)마다 조건을 만족하면 결과에 반영
• 조건 변형
  • n += 1
    - 좌표의 개수는 n+1개이므로, 1을 더해줌
  • (n-y-1, x)
    - 위, 아래, 좌, 우 익숙한 방향으로 사용하기 위해 변형
• 함수
  
  • add
    - 추가했을 때 조건을 만족하면 추가한 채로 True
  • remove
    - 제거했을 때 조건을 만족하면 제거한 채로 False
  • satisfied
    - 현재 건축물(기둥/보)들이 모든 조건을 만족하면 True

 

다른 사람이 작성한 코드

def impossible(result):
    COL, ROW = 0, 1
    for x, y, a in result:
        if a == COL: # 기둥일 때
            if y != 0 and (x, y-1, COL) not in result and \
        (x-1, y, ROW) not in result and (x, y, ROW) not in result:
                return True
        else: # 보일 때
            if (x, y-1, COL) not in result and (x+1, y-1, COL) not in result and \
        not ((x-1, y, ROW) in result and (x+1, y, ROW) in result):
                return True
    return False

def solution(n, build_frame):
    result = set()
    
    for x, y, a, build in build_frame:
        item = (x, y, a)
        if build: # 추가일 때
            result.add(item)
            if impossible(result):
                result.remove(item)
        elif item in result: # 삭제할 때
            result.remove(item)
            if impossible(result):
                result.add(item)
    answer = map(list, result)
    
    return sorted(answer, key = lambda x : (x[0], x[1], x[2]))

• 전체가 아닌, 각 건축물의 조건을 확인하는 방식

https://velog.io/@tjdud0123/%EA%B8%B0%EB%91%A5%EA%B3%BC-%EB%B3%B4-%EC%84%A4%EC%B9%98-2020-%EC%B9%B4%EC%B9%B4%EC%98%A4-%EA%B3%B5%EC%B1%84-python

기둥과 보 설치 - 2020 카카오 공채 (python)

 

기억해야할 것

• 문제 접근 방식
  
  • 전체 건축 상황을 고려하며 추가/삭제하면 문제가 매우 복잡하다
  • 예를 들어, 기둥을 제거해도 되는지 확인할 때
    - 기둥 위에 보가 있는지 확인
    - 보가 있으면 보가 다른 보와 연결되어 있는지 확인
    - 연결된 보들이 모두 기둥 조건을 만족하는지 확인
  • 탐색이 정형화되지 않는 복잡한 문제에 대해, 간단하게 정형화할 수 있는 방법을 꼭 찾아야한다