📌 프로그래머스 [거리두기 확인하기]
🔗 문제 링크
문제 설명 📄
5×5 크기의 대기실 places 리스트가 주어진다.
응시자(P)들이 거리두기를 준수하는지 확인해야 한다.
단, 파티션(X)이 있으면 거리 제한을 무시할 수 있다.
모든 대기실이 거리두기를 지키면 1, 그렇지 않으면 0을 반환한다.
문제 접근 방식 💡
- 대기실을 순회하며 응시자(P)가 있는 위치를 탐색.
- 상하좌우(pattern)를 이동하며 거리두기 준수 여부 검사.
- 거리가 2인 위치도 추가 검사하여 파티션(X) 여부 체크.
Solution 💻
def solution(places):
pattern = [(0,1), (1,0), (0,-1), (-1,0)]
def judg(place, x, y):
for px, py in pattern:
dx, dy = px + x, py + y
if 0 <= dx < 5 and 0 <= dy < 5:
if place[dx][dy] == "P":
return False
elif place[dx][dy] == "X":
continue
else:
for kx, ky in pattern:
jx, jy = dx + kx, dy + ky
if (jx, jy) != (x, y) and 0 <= jx < 5 and 0 <= jy < 5:
if place[jx][jy] == "P":
return False
return True
def distance(place):
for i in range(5):
for j in range(5):
if place[i][j] == "P":
if not judg(place, i, j):
return 0
return 1
answer = []
for place in places:
answer.append(distance(place))
return answer
시간 복잡도 분석 ⏲️
- 시간 복잡도: O(5×5×4) = O(100)
- 5×5 대기실을 순회 (O(25))
- 각 P에서 4방향 탐색 (O(4))
- 최대 O(100) 연산으로 충분히 빠름.
- 공간 복잡도: O(1)
- 추가적인 데이터 구조를 사용하지 않음.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| 프로그래머스 [후보 키] (0) | 2025.03.04 |
|---|---|
| 프로그래머스 [문자열 압축] (0) | 2025.03.04 |
| 프로그래머스 [서버 증설 횟수] (0) | 2025.03.01 |
| 프로그래머스 [디펜스 게임] (0) | 2025.02.19 |
| 프로그래머스 [리코쳇 로봇] (1) | 2025.02.18 |