https://programmers.co.kr/learn/courses/30/lessons/60061
카카오 코테 문제에 대한 나의 접근 방식 및 풀이를 정리한 것이다.
처음 접근할 때는 2차원 배열을 만들어서 해당 위치에 기둥일 떄는 0, 보일때는 1을 넣고 나머지는 -1을 넣어서 매개변수로 주어진 일들을 다한 다음에 최종적으로 나오는 2차원 배열을 출력하는 방식으로 하려고 하였다.(위와 같이)
그러나 여기서 간과한 사실은 해당 위치에 기둥과 보가 같이 올 수 있다는 것이다. 이러한 경우에는 0과 1이 동시에 있어야 하고 이렇게 되면 코드가 매우 복잡해지고 비효율적이게 되어서 접근 방식이 잘못되었다고 생각했다.
def make_ck(graph, work):
x = work[0]
y = work[1]
stuff = work[2]
if stuff == 1 : # 보를 설치하는 경우
if y == 0: # 바닥이면 바로 False 리턴
return False
if graph[x][y - 1] == 0: # 아래가 기둥안 경우
return True
elif ((x > 0 and y > 0) and graph[x - 1][y - 1] == 0) or ((x < len(graph) and y > 0) and graph[x + 1][y - 1] == 0): # 왼쪽 아래 또는 오른쪽 아래가 기둥인 경우
return True
elif x > 0 and graph[x - 1][y] == 1 and graph[x + 1][y] == 1 :# 왼쪽과 오른쪽이 보인 경우
return True
elif stuff == 0: # 기둥을 설치하는 경우
if y == len(graph): # 꼭대기이면 바로 False 리턴
return False
if y == 0: # 바닥에 설치하는 경우
return True
elif graph[x][y - 1] == 0: # 아래가 기둥인 경우
return True
elif graph[x - 1][y - 1] == 0 or graph[x + 1][y - 1] == 0: # 보의 한쪽 끝인경우
return True
return False
def solution(n, build_frame):
graph = [[-1]* (n + 1) for _ in range(n + 1)]
for work in build_frame:
x = work[0]
y = work[1]
stuff = work[2]
build = work[3]
if make_ck(graph, work): # 설치 가능한 경우
if build == 1: # 설치 하려는 경우
if stuff == 0: # 기둥인 경우
graph[x][y] = 0
elif stuff == 1: # 보인 경우
graph[x][y] = 1
else : # 철거 하려는 경우
graph[x][y] = -1
return
시간을 더 투자해서 풀어보려고 생각을 했으나 시간이 너무 걸리고 있어서 그냥 해설을 보았는데 너무 쉬워서 허탈했다. 이 문제를 꼭 이차원 배열로 풀려고 접근한 건 아닌지 생각해보게 되었다. 그냥 answer 이라는 배열에 넣고 그 배열에 안에 있는지 확인하면 되는데 이차원 배열을 활용할 생각에 너무 복잡하게 생각한 것 같다. 그리고 한번 넣을 떄 마다 모두 가능한지 확인하는 것은 너무 비효율적이라고 생각해서 안했는데 문제에 주어지 시간과 메모리를 보면 충분히 접근할 수 있는 방법인데 너무 배제하고 생각한 것 같아서 다음에는 주어진 시간도 잘 봐야겠다고 생각했다.
def possible(answer):
for x, y, stuff in answer:
if stuff == 0: # 기둥인 경우 (바닥인경우, 아래에 기둥이 있는 경우, 왼쪽에 보가 있는 경우, 본인 자리에 보가 있는 경우 )
if y == 0 or [x, y - 1 , 0] in answer or [x, y, 1] in answer or [x - 1, y, 1] in answer:
continue
return False
else: # 보인경우 (밑에 기둥이 있는 경우, 오른쪽 아래가 기둥인경우, 왼쪽과 오른쪽이 보인 경우)
if [x, y - 1, 0] in answer or [x + 1, y - 1, 0] in answer or ([x - 1, y , 1] in answer and [x + 1, y, 1] in answer):
continue
return False
return True
def solution(n, build_frame):
answer = []
for fram in build_frame:
x, y, stuff, op = fram
if op == 1: # 설치하는 경우
answer.append([x, y, stuff]) # 일단 추가하고 가능한지 확인
if not possible(answer):
answer.remove([x, y, stuff])
elif op == 0: # 제거하는 경우
answer.remove([x, y, stuff]) # 일단 제거하고 가능한지 확인
if not possible(answer):
answer.append([x, y, stuff])
answer.sort()
return answer