시험을 앞두고 계속 카카오 기출 문제를 풀고 있습니다.
이번 문제는 프로그래머스 Lv.3 기둥과 보 설치 문제입니다.
문제는 시뮬레이션 문제인데요. 주어진 벽면에 기둥 또는 보를 설치하거나 철거하는 명령이 들어오면 기둥이나 보의 조건에 맞는지 검사한 후 설치하거나 철거한 뒤 최종 결과를 제출하는 문제입니다. 각 구조물의 좌표는 점으로 주어지고 기둥은 점 기준으로 윗 방향으로 지어지며, 보는 점 기준으로 오른쪽 방향으로 지어집니다.
먼저 기둥을 지을 수 있는 조건은 다음과 같습니다.
1) 기둥을 짓는 면이 벽의 바닥이거나 (Y=0)
2) 기둥이 다른 기둥 위에 있거나 ([x, y-1]에 기둥 위치)
3) 기둥이 다른 보의 한쪽 끝에 걸쳐있거나 ([x-1,y] 또는 [x,y]에 보 위치)
다음으로 보를 지을 수 있는 조건은 다음과 같습니다.
1) 보의 한 쪽 끝이 기둥에 닿아있거나 ([x, y-1] 또는 [x+1, y-1]에 기둥 위치)
2) 보를 지을 때 양 쪽 끝의 보에 동시에 접하고 있거나 (짓는 시점에 [x-1, y]과 [x+1, y]에 보가 존재)
def is_possible(result):
col, beam = 0, 1
for x, y, t in result:
if t == col:
# 기둥을 지을 수 있는 조건들
if y == 0 or [x, y-1, col] in result or [x, y, beam] in result or [x-1, y, beam] in result:
continue
else:
return False
else:
# 보를 지을 수 있는 조건들
if [x, y-1, col] in result or [x+1, y-1, col] in result or ([x+1, y, beam] in result and [x-1, y, beam] in result):
continue
else:
return False
return True먼저 위 조건에 해당하는 지 보면서 건물을 짓는것까지는 구현했습니다.
모든 조건 중에 하나라도 해당하면 넘어가고 모두 해당되지 않으면 False하여 건물을 짓거나 철거하지 않습니다.
문제는 철거할 때인데 이 때 저는 이상이 발생할 수 있는 지점들을 모두 체크하는 방식으로 구현해야 된다고 생각했습니다. 전체 구조물을 다 검사하기에는 시간 복잡도에서 불리할 거라 생각했기 때문입니다. 그런데 의외로 그런 방법들이 맞는 경우가 많더라구요. (결과적으로 이 문제도 모든 케이스를 그 때마다 모두 검사합니다) 너무 시간 복잡도에 매몰되면 못푸는 문제가 많은 것 같습니다. 일단 시도해보고 바꾸는 연습을 하는게 맞을 것 같습니다.. 물론 실전에 시간이 많은 시험에서야 가능하겠지만요.
여튼 처음에는 모두 구현했는데 테스트케이스는 통과했지만 제출 시 1~2개 빼고는 다 실패가 떴습니다. 너무 구현하는 데 에너지를 많이 써서 디버깅할 엄두가 나지 않아 코드를 참조하여 방법론을 수정했습니다.
먼저 건설이나 철거 명령이 들어올 때마다 현재까지 있는 구조물을 모두 검사하여 조건을 모두 충족하고 있는지 검사합니다. 지을 때는 사실 상 짓는 구조물이 기존 구조물이 있는 상태에서 지어질 수 있는지를 검사하는 셈이고, 철거할 때는 구조물을 일단 뺀 상태에서 다른 구조물의 건설 조건이 모두 충족되는 지 검사하고 가능하면 철거를 수행한 채로 넘어가고, 아닌 경우에는 다시 철거한 구조물을 포함하는 문제입니다.
def solution(n, build_frame):
answer = []
result = []
for x, y, t, mode in build_frame:
item = [x,y,t]
if mode:
# 일단 짓고 돌려본 다음 불가능하면 빼기
result.append(item)
if not is_possible(result):
result.remove(item)
else:
# 일단 빼고 돌려본 다음 불가능하면 다시 짓기
result.remove(item)
if not is_possible(result):
result.append(item)명령의 개수가 최대 1,000개이므로 전체를 다시 검사한다고 쳐도 O(n^2)이기 때문에 계산 횟수가 1,000,000으로 시간 복잡도가 크게 문제가 되지 않을 것 같습니다. 그렇게 생각했더라면 바로 이런 방법으로 접근했을 것 같습니다.
시뮬레이션 문제들이 전체적으로 이렇게 막막한 면이 있는데 화려한 스킬보다는 진득하고 정직하게 풀다보면 풀리는 경우가 많은 것 같습니다. 자신을 믿고 푸는 연습을 해야겠네요.
시간 복잡도 : O(n^2) , n : 구조물 명령의 개수
why? n개의 명령을 순회할 때 모든 구조물이 지어지는 경우에 지을 때마다 검사하는 구조물의 개수가 1+2+3+...+n 이 되면서 O(n^2)이 될 것 같다.
