[알고리즘] 기둥과 보 설치 문제 풀이 (Python)

문제보기

풀이

처음 문제를 읽고 생각한 풀이는 기둥 설치, 기둥 삭제, 보 설치, 보 삭제 네 가지 경우의 수로 분기 처리해서 각 경우마다 가능한지 판별하고 해당 작업을 수행하는 것이 였습니다.
하지만 이렇게 할 경우 구현해야할 것이 많고 예외 처리해야할 것도 많아서 생각한 방법이 작업을 먼저 수행하고 전체 구조물이 조건을 만족하는지 검사하고 조건을 만족한다면 다음 작업으로 넘어가고 만족하지 못하다면 수행한 작업을 되돌리는 방법입니다.

최적화 방법으로는 구조물 저장을 list를 사용하지 않고 set을 사용해서 탐색, 삭제 속도를 높이는 것 입니다.

코드

def check(answer):
    for x,y,a in answer:
        if a == 0:
            if (x, y-1, 0) in answer or (x-1, y, 1) in answer or (x, y, 1) in answer or y == 0:
                continue
            return False
        else:
            if ((x-1, y, 1) in answer and (x+1, y, 1) in answer) or (x, y-1, 0) in answer or (x+1, y-1, 0) in answer:
                continue
            return False
    return True


def solution(n, build_frame):
    answer = set()
    
    for x, y, a, b in build_frame:
        if b == 1:
            answer.add((x,y,a))
            if not check(answer):
                answer.remove((x,y,a))
        else:
            answer.remove((x,y,a))
            if not check(answer):
                answer.add((x,y,a))
    
    answer = [list(i) for i in answer]
    answer.sort(key=lambda x:(x[0], x[1], x[2]))
    return answer

공부

list와 set의 연산 차이

위 풀이에서 주로 사용하는 연산이 포함(Containment), 삽입, 삭제인데 list와 set의 시간 복잡도를 비교해보면 왜 set을 사용해야 하는지 알수있다.

• list
  • 포함 O(n)
  • 삽입 O(1)
  • 삭제 O(n)
    
• set
  • 포함 O(1)
  • 삽입 O(1)
  • 삭제 O(1)
    

set 내부 원소는 다양한 값을 함께 가질 수 있지만, mutable한 값은 가질수 없다.

>>> s = {"1", 3, 5, (1,3)}
>>> s
{(1, 3), 5, 3, '1'}
>>> s = {"1", 3, 5, [1,3]}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> s = {"1", 3, 5, {1,3}}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'set'
>>> s = {"1", 3, 5, {1:1,3:3}}
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> s = {"1", 3, 5, frozenset([1,3,4])}
>>> s
{5, 3, '1', frozenset({1, 3, 4})}