반응형

프로그래머스 레벨 5 방의 개수를 풀어봤다.
레벨 5중에 정답률이 많이 높은 문제라 도전해 봤는데
실제 난이도는 3~4 정도인 느낌이다.
문제

문제는 위와 같다.
예시로 다음 그림이 주어진다.

이렇게 구역이 나눠지면 그 구역의 개수를 세면 된다.
구현
1차적으로 구역이 생기는 경우는 기존에 방문했던 점을 다시 방문했을 때이다.
이것만 생각했다면 실행할 때 테스트케이스는 맞지만 제출을 하면 다 틀리는 상황을 볼 수 있다.
추가로 확인해야 되는 점은 기존에 연결된 간선이 있는지다.
따라서 기존에 연결된 간선이 없고 방문했던 노드라면 그때 정답의 개수를 추가해 주면 된다.
여기서 대각선의 상황도 추가로 생각해야 한다. 하지만 이 상황은 포인트의 개수를 두배로 늘리며 접근하면 대각선 상황 자체가 사라진다.
아래 코드에서 라인 단위 주석으로 설명하겠다.
코드
from collections import defaultdict
#0번부터 8번까지의 방향을 list로 저장
dy = [-1,-1,0,1,1,1,0,-1]
dx = [0,1,1,1,0,-1,-1,-1]
def solution(arrows):
answer = 0
#방문한 곳 체크용 set
visit = set()
#그린 선 저장용 dict(접근 시간 효율, 중복 제거를 위한 set)
edge = defaultdict(set)
#초기 좌표 값 & 방문 처리
x,y=0,0
visit.add((x,y))
for a in arrows:
#대각선 처리를 위해 두 번 반복
for _ in range(2):
#다음 좌표 계산
nx, ny = x+dx[a], y+dy[a]
#이동할 좌표가 방문했던 점이고 간선이 그려지지 않았을 때
if (nx,ny) in visit and (x, y) not in edge[(nx,ny)]:
#구역 추가
answer+=1
#방문한 점이 아닐 때
elif (nx,ny) not in visit:
#방문처리
visit.add((nx,ny))
#간선 저장
edge[(nx,ny)].add((x, y))
edge[(x,y)].add((nx, ny))
#좌표 업데이트
x,y = nx,ny
return answer
다른 풀이
내가 수학을 좀 더 잘했더라면 아래와 같은 풀이를 할 수 있었을 것이다.
오일러 공식을 사용해 모든 선과 라인을 그리고 라인은 중복되므로
면의 개수 = 중복된 선의 개수//2 - 점의 개수 + 1을 해주면 된다.
def solution(arrows):
answer = 0
point = set()
edge = set()
x,y=0,0
point.add((x,y))
for a in arrows:
for _ in range(2):
nx, ny = x+dx[a], y+dy[a]
point.add((nx,ny))
edge.add((x, y, nx, ny))
edge.add((nx, ny, x, y))
x,y = nx,ny
return len(edge)//2-len(point)+1
이 풀이는 솔직히 시험을 볼 때는 생각이 날 것 같지 않다...
이런 공식들이 바로바로 생각나는 분들이라면 훨씬 빠르게 해결할 수 있을 문제라고 생각된다.
반응형
'Coding Test > Python' 카테고리의 다른 글
[프로그래머스] 두 원 사이의 정수 쌍 Python 풀이 (0) | 2023.04.17 |
---|---|
[Codility] Pi Code Challenge Python (1) | 2023.04.14 |
[프로그래머스] 달리기 경주 Python 풀이 (0) | 2023.04.07 |
[프로그래머스] 추억 점수 Python 풀이 (0) | 2023.04.06 |
[프로그래머스] 바탕화면 정리 Python 풀이 (0) | 2023.04.06 |
댓글