반응형
해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다.
문제설명
하단의 링크를 참조하자.
https://programmers.co.kr/learn/courses/30/lessons/60061
사고과정
- 일반적인 구현문제처럼 2차원 리스트 좌표 평면에서 값을 하나하나씩 갱신하는 것으로 풀으려고 했으나 너무 로직이 복잡해져 다 커버하지 못하고 풀지 못했다..
- 풀이를 보니 2차원 리스트를 쓰긴 썼지만 좌표평면을 사용한 게 아니라 주어지는 정보를 리스트에 담아서 처리하는 방법으로 했다. 구현 문제를 이렇게도 푸는구나를 느끼면서 매우 충격이었다.. 먼저 연산(삭제/설치)를 기준으로 나누어서 기둥/보 설치할 때 가능여부 삭제할 때 가능여부를 탐색하면서 풀었다. 시간 복잡도가 $O(M^3)$이긴 했지만 주어진 시간 제한이 5초이고 주어진 범위가 1000이하히기 때문에 넉넉하게 해결할 수 있다고 한다..
- 그리고 놓치지 말아야 할 점은.. 좌표평면을 사용하지 않았기 때문에 주어지는 x, y 좌표는 문제에서 입출력 예시로 정해준 x, y 축을 그대로 따라 간다. 즉, 파이썬으로 2차원 리스트로 만들어줄때 좌표랑 문제에서 주어지는 좌표랑 공간 기준이 동일하지 않음을 잊지말자!
풀이(스스로 못 푼 풀이)
def check_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
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
return False
return True
def solution(n, build_frame):
answer = []
for frame in build_frame:
x, y, stuff, operate = frame
# 설치인 경우
if operate == 1:
answer.append([x, y, stuff])
if not check_possible(answer): # 설치 후 불가능 경우라면
answer.remove([x, y, stuff])
# 삭제인 경우
if operate == 0:
answer.remove([x, y, stuff])
if not check_possible(answer): # 삭제 후 불가능 경우라면
answer.append([x, y, stuff])
return sorted(answer)
반응형
'알고리즘 삽질장' 카테고리의 다른 글
[이코테] 다이나믹 프로그래밍 - 병사 배치하기 (0) | 2021.10.15 |
---|---|
[이코테] DFS/BFS - 연산자 끼워 넣기 (0) | 2021.10.15 |
[이코테] 그래프 알고리즘 - 어두운 길 (0) | 2021.10.13 |
[이코테] 최단 경로 - 화성 탐사 (0) | 2021.10.13 |
[이코테] 다이나믹 프로그래밍 - 퇴사 (0) | 2021.10.12 |