사용자 도구

사이트 도구


ps:problems:programmers:81302

거리두기 확인하기

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호81302
문제명거리두기 확인하기
레벨Level 2
분류

구현

시간복잡도O(r*c)
인풋사이즈r=5, c=5
사용한 언어Python
해결날짜2021/07/09
출처

ps:problems:programmers:2021_카카오_채용연계형_인턴십

풀이

  • 그냥 구현문제..
  • 모든 셀에 대해서 그 셀에 응시자가 있는 경우, 맨해튼 거리 2 이내의 셀중에 거리두기를 안지킨 응시자가 있는지 확인하면 된다. BFS로 구현할수도 있지만, 그냥 상하좌우로 인접한 셀, 대각선으로 인접한 셀, 상하좌우로 2칸 거리의 셀의 세가지 패턴으로 나누어서 응시자가 있고 파티션이 없는 경우가 있는지를 각각 확인하는 것이 좀더 편리하다.
    • 만약 문제 조건이 맨해튼거리 3이내였다면 BFS로 하는게 편할것이다..
  • 맨해튼 거리 2 이내의 셀의 개수는 상수이므로.. 각 셀에 대해서 거리두기가 지켜지는 지를 찾는것도 O(1)이다. 총 시간복잡도는 O(|셀의 개수|)이지만.. 셀의 개수도 5×5로 고정되어 있으므로 그냥 O(1)이라고 생각해도 되긴 한다.

코드

"""Solution code for "Programmers 81302. 거리두기 확인하기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/81302
- Solution link: http://www.teferi.net/ps/problems/programmers/81302
"""

DELTA = ((1, 0), (0, 1), (-1, 0), (0, -1))


def is_okay(place):
    def is_person_at_pos(r, c):
        return 0 <= r < 5 and 0 <= c < 5 and place[r][c] == 'P'
    
    for r in range(5):
        for c in range(5):
            if not is_person_at_pos(r, c):
                continue
            for (dr1, dc1), (dr2, dc2) in zip(DELTA, DELTA[1:] + DELTA[:1]):
                nr, nc = r + dr1, c + dc1
                nnr, nnc = r + dr1 + dr1, c + dc1 + dc1
                nr2, nc2 = r + dr2, c + dc2
                diag_r, diag_c = r + dr1 + dr2, c + dc1 + dc2
                if is_person_at_pos(nr, nc):
                    return False
                if is_person_at_pos(nnr, nnc) and place[nr][nc] != 'X':
                    return False
                if (is_person_at_pos(diag_r, diag_c) and 
                        (place[nr][nc] != 'X' or place[nr2][nc2] != 'X')):
                    return False            
    return True


def solution(places):
    return [1 if is_okay(x) else 0 for x in places]

토론

댓글을 입력하세요:
V B N F U
 
ps/problems/programmers/81302.txt · 마지막으로 수정됨: 2021/07/10 18:11 저자 teferi