Posts 거리두기 확인하기 [Python]
Post
Cancel

거리두기 확인하기 [Python]

URL https://programmers.co.kr/learn/courses/30/lessons/81302

문제 설명

  • 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
  • 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
  • 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
    • 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
    • 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
    • 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
  • 5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다.
  • 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다.
  • 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

제한 사항

  • places의 행 길이(대기실 개수) = 5
    • places의 각 행은 하나의 대기실 구조를 나타냅니다.
  • places의 열 길이(대기실 세로 길이) = 5
  • places의 원소는 P,O,X로 이루어진 문자열입니다.
    • places 원소의 길이(대기실 가로 길이) = 5
    • P는 응시자가 앉아있는 자리를 의미합니다.
    • O는 빈 테이블을 의미합니다.
    • X는 파티션을 의미합니다.
  • 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
  • return 값 형식
    • 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
    • places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
    • 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.

문제 풀이

  • check_p 함수로 place에서 P의 위치를 가져옴
  • manhattan_distance로 거리를 구함
    • 거리가 만약 1이라면 P와 P가 서로 붙어있는것이기 때문에 무조건 0을 리턴
    • 거리가 2라면 P와 P는 한칸 떨어져있고, 떨어진 중간에 파티션이 있는지 체크해야함
  • check_middle 함수로 거리가 2인것들에 대해서만 사이에 X가 있는지 확인함
    • x,y 좌표를 잘 구해야함 (0, 0), (0, 2) -> (0, 1)을 체크, (0, 0), (2, 0) 일때 (1, 0)을 체크해서 X가 있는지 확인
  • check_cross 함수로 파티션이 대각선에 모두 있는지 확인
  • 3개중에 하나라도 걸리면 0을 리턴해서 answer에 0을 append, 모두 통과하면 거리두기를 잘 지키는것으로 1을 append함

  • 이 문제푸는데 2일걸림.. 알고리즘 공부가 시급한듯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
import itertools

def manhattan_distance(a,b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

def check_p(place):
    p=[]
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                p.append((i,j))
    return p

def check_middle(c, d, place):
    # 같은 행일때 x
    if c[0] == d[0]:
        x = c[0]
    # 다른 행일때 x
    else :
        x = int((c[0] + d[0])/ 2)
    # 같은 열일때 y
    if c[1] == d[1]:
        y = d[1]
    # 다른 열일떄 y
    else :
        y = int((c[1] + d[1] )/ 2)
        
    if place[x][y] != 'X':
        return 0

def check_cross(c, d, place):
    if place[c[0]][d[1]] != 'X' or place[d[0]][c[1]] != 'X':
        return(0) 
    
def check_distance(place):
    p = check_p(place)
    distance1 = []
    distance2 = []
    
    for a, b in itertools.combinations(p, 2):
        # 맨하튼 거리가 1이면 상하좌우 어딘가에 있단 이야기이므로 무조건 거리두기가 지켜지지않음
        if manhattan_distance(a, b) == 1:
            distance1.append((a, b))
        # 맨하튼 거리가 2이면 한칸띄어서 혹은 대각선에 P가 있음
        elif manhattan_distance(a, b) == 2:
            distance2.append((a, b))
    if len(distance1) > 0:
        return 0

    for c, d in distance2:
        # 거리가 2인 조합에서 middle에 파티션이 있는지 확인
        if abs(c[0] - d[0]) ==0 or abs(c[1] - d[1]) == 0:
            if check_middle(c, d, place) == 0:
                return 0
        # 거리가 2인 조합에서 대각선에 파티션이 있는지 확인
        elif check_cross(c, d, place) == 0:
            return 0
    return 1

def solution(places):
    answer = []
    for place in places:
        y = check_distance(place)
        answer.append(y)
    return answer
1
2
3
4
5
6
places = [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], 
          ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], 
          ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], 
          ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], 
          ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]
solution(places)
1
[1, 0, 1, 1, 1]
1
2
places = [["OXPOO", "OPXOO", "OOOOO", "OOOOO", "OOOOO"]]
solution(places)
1
[1]
1
2
places = [["OOOOO", "OOOOO", "OOOOO", "OOOOO", "OOOOO"]]
solution(places)
1
[1]
1
2
places = [["OPPOO", "OOOOO", "OOOOO", "OOOOO", "OOOOO"]]
solution(places)
1
[0]
1
2
places = [["OPOPO", "OOOOO", "OOOOO", "OOOOO", "OOOOO"]]
solution(places)
1
[0]
1
2
places = [["OOPOO", "OPOOO", "OOOOO", "OOOOO", "OOOOO"]]
solution(places)
1
[0]
This post is licensed under CC BY 4.0 by the author.

Sorting Algorithm

방금그곡 [Python]

Comments powered by Disqus.