프로그래머스 [거리두기 확인하기]

📌 프로그래머스 [거리두기 확인하기]

🔗 문제 링크

---

문제 설명 📄

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)
  • 추가적인 데이터 구조를 사용하지 않음.