My Solution
시간이 정말 많이 걸린 문제다. 풀이 계획을 세우고 구현에 들어갔는데, 코드를 다 적고 제출해보니 런타임 오류가 발생하여 문제를 찾는데 시간이 많이 들었다.
런타임 오류가 발생한 부분은 두 곳 정도였다.
- 2차원 배열을 인덱스를 조작하여 접근할때
out of range오류 발생 ans.remove(result)에서 리스트에 없는 원소를 제거하는 오류 발생
두가지 문제를 해결하기 위해 리스트 접근시 인덱스가 유효한지 검증한 뒤 접근했고, remove연산 전 리스트에 원소가 있는지 확인했다.(이 부분은 아래 문제를 해결하니 문제가 발생하지 않았다)
런타임 오류를 잡고 나서 다시 제출해보았는데, 이번에는 많은 테스트케이스가 오답으로 나왔다.
다시 코드를 확인해보니 빼먹은 케이스와 잘못된 검증로직이 들어있었다. 잘못된 검증로직은 예를 들어서
if A or B:에서 A조건이 참이면 B조건은 검증 없이 통과되어버리는데, 이 과정에서 검증이 수행되지 않는 케이스들이 있었다.
또한 초기에는 board라는 2차원 변수에 기둥과 보를 합쳐서 관리했는데, 한 좌표에 기둥과 보가 같이 있을 수 있었기 때문에 이를 vert와 horz로 분리하여 기둥은 vert에, 보는 horz에 저장하여 관리하였다.
이런 종류의 복잡한 구현문제는 문제를 풀기 전 발생할 수 있는 모든 경우를 꼼꼼하게 체크한 뒤에 계획을 세우고 접근하는 것이 시간을 절약할 수 있는 방법인 것 같다. 나름대로 경우의 수를 체크한 다음 코드를 작성하기 시작했는데, 빠진 케이스가 있어서 그 케이스를 찾는데 시간이 많이 소모되었다.
def solution(n, build_frame):
ans = []
vert = [[-1 for _ in range(n+1)] for _ in range(n+1)]
horz = [[-1 for _ in range(n+1)] for _ in range(n+1)]
for x, y, a, b in build_frame:
result = [x, y, a]
x, y = n-y, x
#설치
if b == 1:
if isSafe(n, vert, horz, [x,y,a]):
ans.append(result)
if a == 0 :
vert[x][y] = a
elif a == 1:
horz[x][y] = a
#삭제
elif b == 0:
if result in ans:
ans.remove(result)
if a == 0:
vert[x][y] = -1
flag = False
if x > 0:
if not isSafe(n, vert, horz, [x-1,y,vert[x-1][y]]):
flag = True
if not isSafe(n, vert, horz, [x-1,y,horz[x-1][y]]):
flag = True
if y > 0 and not isSafe(n, vert, horz, [x-1,y-1,horz[x-1][y-1]]):
flag = True
if flag:
vert[x][y] = a
ans.append(result)
elif a == 1:
horz[x][y] = -1
flag = False
if not isSafe(n, vert, horz, [x,y,vert[x][y]]):
flag = True
if y < n:
if not isSafe(n, vert, horz, [x,y+1,vert[x][y+1]]):
flag = True
if not isSafe(n, vert, horz, [x,y+1,horz[x][y+1]]):
flag = True
if y > 0 and not isSafe(n, vert, horz, [x,y-1,horz[x][y-1]]):
flag = True
#복구
if flag:
horz[x][y] = a
ans.append(result)
ans.sort(key = lambda x : (x[0], x[1], x[2]))
return ans
def isSafe(n, vert, horz, build):
x, y, a = build
#기둥
if a == 0:
if x == n:
return True
elif x < n and vert[x+1][y] == 0:
return True
elif horz[x][y] == 1:
return True
elif y > 0 and horz[x][y-1] == 1:
return True
#보
elif a == 1:
if y < n and (vert[x+1][y] == 0 or vert[x+1][y+1] == 0):
return True
elif (y > 0 and horz[x][y-1] == 1) and (y < n and horz[x][y+1] == 1):
return True
#아무것도 없음
elif a == -1:
return True
return False
#디버깅용
def printBoard(vert, horz):
for i in range(len(vert)):
for j in range(len(vert)):
x = vert[i][j] if vert[i][j] != -1 else horz[i][j]
print(x, end=" ")
print()
print()Better Solution
내 답안과 달리 2차원 배열이 아니라 answer에 연결리스트 형태로 직접 저장하여 로직이 훨씬 단순해졌다. 2차원 배열로 만들때는 좌표도 변환하고 인덱스가 넘어가는 경우도 신경써야 했는데, 연결리스트를 사용한 방법에서는 단순히 원소가 리스트에 있는지 비교하기만 하면 되기 때문에 케이스만 잘 구분하면 쉽게 구현할 수 있다.
def possible(answer):
for x, y, stuff in answer:
if stuff == 0: # 기둥인 경우
if (y == 0 # 바닥이거나
or [x-1,y,1] in answer # 보의 오른쪽 끝이거나
or [x,y,1] in answer # 보의 왼쪽 끝이거나
or [x,y-1,0] in answer): # 아래가 기둥이면
continue # 다음 stuff 확인
return False # 조건을 만족하지 않으면 불가능
elif stuff == 1: # 보인경우
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 # 다음 stuff 확인
return False # 조건을 만족하지 않으면 불가능
return True # 모든 stuff가 통과했으면 가능
def solution(n, build_frame):
answer=[]
for frame in build_frame:
x, y, stuff, operate = frame
if operate == 0: # 삭제하는 경우
answer.remove([x,y,stuff]) # 일단 지우고
if not possible(answer): # 불가능하면
answer.append([x,y,stuff]) # 복구
if operate == 1: # 설치하는 경우
answer.append([x,y,stuff]) # 일단 추가하고
if not possible(answer): # 불가능하면
answer.remove([x,y,stuff]) # 복구
return sorted(answer)- 2020 KAKAO BLIND RECRUITMENT 기둥과 보 설치
- 출처 : 이것이 취업을 위한 코딩테스트다 with 파이썬
