[프로그래머스] 거리두기 확인하기 (Python) - 2021 카카오 채용연계형 인턴십 - 구현

1. 문제 설명

개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.

코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.

 

• 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
• 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
• 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

 

예를 들어,

5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

---

2. 제한사항

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

---

3. 입출력 예

places	result
[["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"]]	[1, 0, 1, 1, 1]

 

---

4. 나의 풀이

다른 공부를 하다 와서 오랜만에 블로그에 글을 올린다...! 부스트캠프 덕에 블로그 조회수가 높아졌을 때 열심히 노를 저었어야 했는데 초큼 아쉽다 ୧(﹒︠ᴗ﹒︡)୨
이 문제는 단순 구현 문제로 판단하고 풀었었다. 거리두기를 지키지 않은 경우를 두가지로 나누어서 풀면 간단하다.

• 응시자가 앉은 자리(P)를 기준으로 앞,뒤,양,옆에 다른 응시자가 있는지 확인
• 응시자가 앉은 자리(P)를 기준으로 대각선에 다른 응시자가 있되, 앞,뒤,양,옆에 파티션이 존재하는지 확인

게다가 교실의 대기실의 크기가 5 x 5로 고정되어 있기 때문에 대략 O(n^2)+α로 풀어도 무방하다.

 

def firstCheck(place):
    for i in place:
        if "POP" in i:
            return False
    temp = list(map(list, zip(*[list(i) for i in place])))
    for i in temp:
        joined = ''.join(i)
        if "POP" in joined:
            return False
    return True

def secondCheck(place):
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    dx2 = [1, -1, 1, -1]
    dy2 = [1, -1, -1, 1]
    place = [list(i) for i in place]
    for i in range(5):
        for j in range(5):
            if place[i][j] == 'P':
                for k in range(4):
                    x = i + dx[k]
                    y = j + dy[k]
                    if 0<=x<5 and 0<=y<5 and place[x][y] == 'P':
                        return False
                for l in range(4):
                    x = i + dx2[l]
                    y = j + dy2[l]
                    if 0<=x<5 and 0<=y<5 and place[x][y] == 'P' and (place[x][j] == "O" or place[i][y] == "O"):
                        return False
    return True

def solution(places):
    answer = []
    for i in places:
        if firstCheck(i) == False or secondCheck(i) == False:
            answer.append(0)
            continue
        answer.append(1)
        
    return answer

 

 

 

 

 

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

코딩테스트 연습 - 거리두기 확인하기