기둥과 보 설치 풀이
너무 어려워서 5명 정도 다른사람이 푼 코드를 보고 공부해서 다시 짰습니다. 머리가 멍청하면 몸이 고생한다는 말이 괜히 있는게 아니었습니다. 문제에서 알려주는 제한사항은 꼭 꼼꼼하게 3~4번 읽고 코드를 작성해야 한다는 사실을 깨달았습니다.
코드
def solution(n, build_frame):
global N
N = n
answer = []
for frame in build_frame :
if frame[3] == 1 : # 설치
answer.append(frame[:-1])
if not check_rule(answer) : answer.pop() # 설치 규칙에 위배되면 넣은거 pop
else : # 삭제
del answer[answer.index(frame[:-1])]
if not check_rule(answer) : answer.append(frame[:-1]) # 삭제 규칙에 위배되면 다시 삽입
answer.sort()
return answer
def check_rule(answer) :
for frame in answer :
x, y, structure = frame
if x < 0 or y < 0 or x > N or y > N : return False
if structure == 0 :
if y == 0 or [x, y, 1] in answer or [x-1, y, 1] in answer or [x, y-1, 0] in answer : continue
else : 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
else : return False
return True
문제에 관하여
제가 처음 접근한 방식은 2x2 board에 설치/삭제 에 대한 표시를하고 공사를 할 때마다 board를 최신화 시켜주려 했지만 하나를 설치하고 제거 할 때마다 위아래양옆으로 계속 설치/삭제 가 바뀌니 돌아버릴 지경이었습니다. 그렇게 다른 사람의 풀이를 보고 깨달음을 얻어서 문제를 풀었습니다.
이 문제의 핵심, 아니 모든 문제의 핵심은 지문을 잘 읽고 기억해서 이용해야합니다.
- 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.
- 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다.
설치/삭제를 일단 한 뒤에, 전체 구조물 검사를 통해 규칙에 위배되지 않으면 다음 공사를 하고, 위배된다면 방금한 공사를 취소하면 됩니다. 이게 핵심입니다.
solution
def solution(n, build_frame):
global N
N = n
answer = []
for frame in build_frame :
if frame[3] == 1 : # 설치
answer.append(frame[:-1])
if not check_rule(answer) : answer.pop() # 설치 규칙에 위배되면 넣은거 pop
else : # 삭제
del answer[answer.index(frame[:-1])]
if not check_rule(answer) : answer.append(frame[:-1]) # 삭제 규칙에 위배되면 다시 삽입
answer.sort() # 건설내용은 정렬해서 리턴해야함
return answer
check_rule
def check_rule(answer) :
for frame in answer :
x, y, structure = frame
if x < 0 or y < 0 or x > N or y > N : return False # 공사장 밖에 건설하는 경우 False
if structure == 0 : # 기둥 검사
if y == 0 or [x, y, 1] in answer or [x-1, y, 1] in answer or [x, y-1, 0] in answer : continue
else : 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
else : return False
return True
일단 build_frame의 원소를 반복문을 통해 answer에 집어넣고, answer가 규칙에 위배되는지를 확인합니다.
코드를 보시면알겠지만 규칙 그 자체입니다. 그 어떠한 추가 설정을 하지 않고 반복문을 통해 answer가 규칙에 위배되는지를 검사하였습니다.
이 문제는 문제를 풀기위한 추가개념이 딱히 필요없는 문제여서 주석에 설명을 달아놓고 여기까지 하도록 하겠습니다.