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

문제 설명

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

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

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

예를 들어,

위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다.

위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다.

위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다.

응시자가 앉아있는 자리(P)를 의미합니다.

빈 테이블(O)을 의미합니다.

파티션(X)을 의미합니다.

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을 담습니다.

입출력 예

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]

입출력 예 설명

입출력 예 #1

첫 번째 대기실

No.	0	1	2	3	4
0	P	O	O	O	P
1	O	X	X	O	X
2	O	P	X	P	X
3	O	O	X	O	X
4	P	O	X	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실

No.	0	1	2	3	4
0	P	O	O	P	X
1	O	X	P	X	P
2	P	X	X	X	O
3	O	X	X	X	O
4	O	O	O	P	P

• (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
• (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.

세 번째 대기실

No.	0	1	2	3	4
0	P	X	O	P	X
1	O	X	O	X	P
2	O	X	P	O	X
3	O	X	X	O	P
4	P	X	P	O	X

• 모든 응시자가 거리두기를 지키고 있습니다.

네 번째 대기실

No.	0	1	2	3	4
0	O	O	O	X	X
1	X	O	O	O	X
2	O	O	O	X	X
3	O	X	O	O	X
4	O	O	O	O	O

• 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.

다섯 번째 대기실

No.	0	1	2	3	4
0	P	X	P	X	P
1	X	P	X	P	X
2	P	X	P	X	P
3	X	P	X	P	X
4	P	X	P	X	P

• 모든 응시자가 거리두기를 지키고 있습니다.

두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.

제한시간 안내

• 정확성 테스트 : 10초

※ 공지 - 2022년 4월 25일 테스트케이스가 추가되었습니다.

두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.

풀이

• 거리두기 문제를 처음 봤을 때는
  • 영역 구분해서 검사할 애들 골라내고,
  • 애들끼리 거리 계산하고,
  • 인접이면 길찾기하고
  • 막 그런... 복잡한 생각을 했는데,
• 풀다보니까 그냥 문자열로 비교하면 되잖아?
  • 싶어서 2중 for문 3번으로 통과
  • 버티컬은 배열을 90도 회전시켜서 해결...
  • 박스는 그냥 노가다로... ㅡ.ㅡ;

def solution(places):
    answer = [1] * 5
    h_check_patterns = ["PP", "POP"]
    v_checks_patterns = ["PP", "POP"]
    box_checks_patterns = [("PO","OP"),("PX","OP"),("PO","XP"),("OP","PO"),("XP","PO"),("OP","PX")]
    places_90d_r = []
    
    for i in range(5):
        for j in range(5):
            if answer[i] == 0:
                break
            for h_chk in h_check_patterns:
                if h_chk in places[i][j]:
                    answer[i] = 0
                    break
                                 
    for i in range(5):
        _tmp = []
        for j in range(5):
            _t = ""
            for k in range(5):
                _t += places[i][k][j]
            _tmp.append(_t)
        places_90d_r.append(_tmp)
        
    for i in range(5):
        for j in range(5):
            if answer[i] == 0:
                break
            for h_chk in h_check_patterns:
                if h_chk in places_90d_r[i][j]:
                    answer[i] = 0
                    break
                    
    for i in range(5):
        for j in range(4):
            if answer[i] == 0:
                break
            for k in range(4):
                for b_chk in box_checks_patterns:
                    if places[i][j][k]+places[i][j][k+1] == b_chk[0] and places[i][j+1][k]+places[i][j+1][k+1] == b_chk[1]:
                        answer[i] = 0
                        break
        
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.21ms, 10.1MB)
테스트 2 〉	통과 (0.12ms, 10.4MB)
테스트 3 〉	통과 (0.09ms, 10.4MB)
테스트 4 〉	통과 (0.15ms, 10.4MB)
테스트 5 〉	통과 (0.05ms, 10.2MB)
테스트 6 〉	통과 (0.08ms, 10.3MB)
테스트 7 〉	통과 (0.10ms, 10.2MB)
테스트 8 〉	통과 (0.09ms, 10.3MB)
테스트 9 〉	통과 (0.06ms, 10.3MB)
테스트 10 〉	통과 (0.05ms, 10.3MB)
테스트 11 〉	통과 (0.09ms, 10.4MB)
테스트 12 〉	통과 (0.09ms, 10.2MB)
테스트 13 〉	통과 (0.10ms, 10.3MB)
테스트 14 〉	통과 (0.09ms, 10.2MB)
테스트 15 〉	통과 (0.08ms, 10.2MB)
테스트 16 〉	통과 (0.22ms, 10.3MB)
테스트 17 〉	통과 (0.63ms, 10.2MB)
테스트 18 〉	통과 (0.05ms, 10.4MB)
테스트 19 〉	통과 (0.10ms, 10.4MB)
테스트 20 〉	통과 (0.09ms, 10.3MB)
테스트 21 〉	통과 (0.05ms, 10.2MB)
테스트 22 〉	통과 (0.05ms, 10.4MB)
테스트 23 〉	통과 (0.21ms, 10.3MB)
테스트 24 〉	통과 (0.03ms, 10.4MB)
테스트 25 〉	통과 (0.22ms, 10.2MB)
테스트 26 〉	통과 (0.29ms, 10.4MB)
테스트 27 〉	통과 (0.10ms, 10.3MB)
테스트 28 〉	통과 (0.27ms, 10.2MB)
테스트 29 〉	통과 (0.21ms, 10.2MB)
테스트 30 〉	통과 (0.20ms, 10.3MB)
테스트 31 〉	통과 (0.15ms, 10.4MB)

• 고수의 풀이.
  • 비슷한 방식

def check(place):
    for irow, row in enumerate(place):
        for icol, cell in enumerate(row):
            if cell != 'P':
                continue
            if irow != 4 and place[irow + 1][icol] == 'P':
                return 0
            if icol != 4 and place[irow][icol + 1] == 'P':
                return 0
            if irow < 3 and place[irow + 2][icol] == 'P' and place[irow + 1][icol] != 'X':
                return 0
            if icol < 3 and place[irow][icol + 2] == 'P' and place[irow][icol + 1] != 'X':
                return 0
            if irow != 4 and icol != 4 and place[irow + 1][icol + 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol + 1] != 'X'):
                return 0
            if irow != 4 and icol != 0 and place[irow + 1][icol - 1] == 'P' and (place[irow + 1][icol] != 'X' or place[irow][icol - 1] != 'X'):
                return 0
    return 1

def solution(places):
    return [check(place) for place in places]
    
정확성  테스트
테스트 1 〉	통과 (0.05ms, 10.2MB)
테스트 2 〉	통과 (0.02ms, 10.2MB)
테스트 3 〉	통과 (0.02ms, 10.4MB)
테스트 4 〉	통과 (0.03ms, 10.3MB)
테스트 5 〉	통과 (0.02ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 10.1MB)
테스트 7 〉	통과 (0.02ms, 10.4MB)
테스트 8 〉	통과 (0.07ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.1MB)
테스트 11 〉	통과 (0.02ms, 10.4MB)
테스트 12 〉	통과 (0.01ms, 10.3MB)
테스트 13 〉	통과 (0.03ms, 10.4MB)
테스트 14 〉	통과 (0.02ms, 10.2MB)
테스트 15 〉	통과 (0.02ms, 10.3MB)
테스트 16 〉	통과 (0.02ms, 10.2MB)
테스트 17 〉	통과 (0.03ms, 10.3MB)
테스트 18 〉	통과 (0.01ms, 10.4MB)
테스트 19 〉	통과 (0.01ms, 10.3MB)
테스트 20 〉	통과 (0.02ms, 10.3MB)
테스트 21 〉	통과 (0.01ms, 10.2MB)
테스트 22 〉	통과 (0.02ms, 10.4MB)
테스트 23 〉	통과 (0.01ms, 10.4MB)
테스트 24 〉	통과 (0.01ms, 10.2MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
테스트 26 〉	통과 (0.02ms, 10.2MB)
테스트 27 〉	통과 (0.03ms, 10.1MB)
테스트 28 〉	통과 (0.04ms, 10.2MB)
테스트 29 〉	통과 (0.02ms, 10.4MB)
테스트 30 〉	통과 (0.02ms, 10.2MB)
테스트 31 〉	통과 (0.01ms, 10.2MB)

• 또 다른 고수의 풀이
  • 재귀호출 길찾기

def solution(places):
    result = []
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    def f(i, j, cnt):
        nonlocal good
        if cnt >2 : return
        if -1<i<5 and -1<j<5:
            if graph[i][j] == 'X':
                return

            if cnt != 0 and graph[i][j] == 'P':
                good = 0
                return

            graph[i][j] = 'X'

            for w in range(4):
                ni = i+dx[w]
                nj = j+dy[w]
                f(ni, nj, cnt+1)

    for case in places:
        graph = [list(r) for r in case]
        good = 1
        for i in range(5):
            for j in range(5):
                if graph[i][j]=='P':
                    f(i,j,0)

        result.append(good)
    return result
    
정확성  테스트
테스트 1 〉	통과 (0.20ms, 10.4MB)
테스트 2 〉	통과 (0.08ms, 10.3MB)
테스트 3 〉	통과 (0.11ms, 10.4MB)
테스트 4 〉	통과 (0.09ms, 10.2MB)
테스트 5 〉	통과 (0.11ms, 10.2MB)
테스트 6 〉	통과 (0.20ms, 10.2MB)
테스트 7 〉	통과 (0.20ms, 10.2MB)
테스트 8 〉	통과 (0.15ms, 10.2MB)
테스트 9 〉	통과 (0.17ms, 10.3MB)
테스트 10 〉	통과 (0.17ms, 10.2MB)
테스트 11 〉	통과 (0.16ms, 10.3MB)
테스트 12 〉	통과 (0.14ms, 10.3MB)
테스트 13 〉	통과 (0.25ms, 10.2MB)
테스트 14 〉	통과 (0.12ms, 10.1MB)
테스트 15 〉	통과 (0.10ms, 10.3MB)
테스트 16 〉	통과 (0.06ms, 10.4MB)
테스트 17 〉	통과 (0.12ms, 10.1MB)
테스트 18 〉	통과 (0.15ms, 10.2MB)
테스트 19 〉	통과 (0.13ms, 10.4MB)
테스트 20 〉	통과 (0.09ms, 10.2MB)
테스트 21 〉	통과 (0.09ms, 10.4MB)
테스트 22 〉	통과 (0.09ms, 10.2MB)
테스트 23 〉	통과 (0.02ms, 10.2MB)
테스트 24 〉	통과 (0.23ms, 10.2MB)
테스트 25 〉	통과 (0.04ms, 10.3MB)
테스트 26 〉	통과 (0.04ms, 10.1MB)
테스트 27 〉	통과 (0.08ms, 10.2MB)
테스트 28 〉	통과 (0.09ms, 10.2MB)
테스트 29 〉	통과 (0.10ms, 10.1MB)
테스트 30 〉	통과 (0.05ms, 10.3MB)
테스트 31 〉	통과 (0.13ms, 10.3MB)

 

 

• 삽질하던 기록...
  • 항상 2D로 그리는 버릇이 있는데 고쳐야 할 듯

def solution(places):
    answer = [0] * 5
    people = []
    rooms = [[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)]

    checks = (((-1,0),(-1,0)),((-1,0),(0,1)),((0,1),(-1,0)),((0,1),(0,1)),((0,1),(1,0)),((1,0),(0,1)),((1,0),(1,0)),((1,0),(0,-1)),((0,-1),(1,0)),((0,-1),(0,-1)),((0,-1),(1,0)),((1,0),(0,-1)))
    
    def check_around(ri, yi, xi):
        for chk in checks:
            for y,x in chk:
                if yi+y < 0:
                    continue
                if xi+x < 0:
                    continue
                if yi+y > 4:
                    continue
                if yi+y > 4:
                    continue
                if places[ri][yi+y][xi+x] == "P":
                    print(ri, yi+y,xi+x,"사람있다")
                    return False
        return True
    
    next_room = 0
    for ri, room in enumerate(places):
        print(ri, next_room)
        if ri == next_room:
            for yi in range(5):
                for xi in range(5):
                    if "P" == places[ri][yi][xi]:
                        if check_around(ri, yi, xi) ==  False:
                            answer[ri] = 0
                            next_room += 1
                            break
                if ri != next_room:
                    break
    print(rooms)
    return answer

def solution(places):
    answer = [0] * 5
    people = []
    대기실 = [[[0 for _ in range(5)] for _ in range(5)] for _ in range(5)]
    
    for ri, room in enumerate(places):
        for yi in range(5):
            for xi in range(5):
                # 대기실[ri][yi][xi] = places[ri][yi][xi]
                if "P" == places[ri][yi][xi]:
                    people.append((ri, yi, xi))
    
    def dfs(ri, yi, xi, cnt):
        cnt -= 1
        if cnt == 0:
            return True
        if places[ri][yi][xi] == "P":
            return False
        elif places[ri][yi][xi] == "O":
            대기실[ri][yi][xi] = 1
            if cnt == 0:
                return True
            else:
                if yi + 1 < 5:
                    if dfs(ri, yi+1, xi, cnt) == False:
                        return False
                if xi + 1 < 5:
                    if dfs(ri, yi, xi+1, cnt) == False:
                        return False
                if yi > 0:
                    if dfs(ri, yi-1, xi, cnt) == False:
                        return False
                if xi > 0:
                    if dfs(ri, yi, xi-1, cnt) == False:
                        return False
                return True

    def draw_room(ri):
        print("룸:",ri)
        for y in range(5):
            for x in range(5):
                print(대기실[ri][y][x],end=" ")
            print("")
        print("="*10)

    next_room = 0
    for ri, yi, xi in people:
        answer[ri] = 1
        if next_room == ri:
            if dfs(ri, yi, xi, 2) == False:
                answer[ri] = 0
                next_room += 1
        if next_room == 5:
            break
        draw_room(ri)

    #print(대기실)
    return answer

def solution(places):
    answer = [0] * 5
    area_of_places = []
    man_of_places = []
    cnt_of_area = 0
    area_set = {0:0}
    
    for ri,r in enumerate(places):
        _tmp = []
        for yi,y in enumerate(r):
            _t = list(y.replace("P","O"))
            for xi in range(5):
                if places[ri][yi][xi] == "P":
                    man_of_places.append([ri, yi, xi, 0]) # Room, Y좌표, X좌표, 감염여부
            _tmp.append(_t)
        area_of_places.append(_tmp)
    
    def dfs(r,y,x):
        area_of_places[r][y][x] = cnt_of_area
        if 0<x and area_of_places[r][y][x-1] == "O":
            dfs(r,y,x-1)
        if 0<y and area_of_places[r][y-1][x] == "O":
            dfs(r,y-1,x)
        if x<4 and area_of_places[r][y][x+1] == "O":
            dfs(r,y,x+1)
        if y<4 and area_of_places[r][y+1][x] == "O":
            dfs(r,y+1,x)
        return
    
    for ri,r in enumerate(places):
        for yi in range(5):
            for xi in range(5):
                if area_of_places[ri][yi][xi] == "O":
                    dfs(ri,yi,xi)
                    cnt_of_area += 1
    
    for i,(r,y,x,m) in enumerate(man_of_places):
        man_of_places[i][3] = area_of_places[r][y][x]
        try:
            area_set[man_of_places[i][3]] += 1
        except:
            area_set[man_of_places[i][3]] = 1
    
    for k, v in list(area_set.items()):
        if v <= 1:
            del area_set[k]
    
    for i in reversed(range(len(man_of_places))):
        if man_of_places[i][3] not in area_set:
            man_of_places.pop(i)
        
    man_of_places.sort(key=lambda x:x[3])
    print(man_of_places)
    print(area_set)
    
    # for ri,r in enumerate(area_of_places):
    #     for yi,y in enumerate(r):
    #         for xi,x in enumerate(y):
    #             print(area_of_places[ri][yi][xi],end=" ")
    #         print("")
    #     print("="*10)
    # answer[0] = 1
    return answer

• 생각해보니 풀이 방법이 여러가지로 해결할 수 있는 문제가 변별력이 더 높을 듯 하다.
  • 그러면 나처럼 노가다로 푸는 무지성 코더들은 다... ㅠ.ㅠ
  • 90도 회전을 마지막에 넣는 것도 괜찮지 않나 싶었는데 5x5크기라 별 차이 없다.

def solution(places):
    answer = [1] * 5
    h_check_patterns = ["PP", "POP"]
    v_checks_patterns = ["PP", "POP"]
    box_checks_patterns = [("PO","OP"),("PX","OP"),("PO","XP"),("OP","PO"),("XP","PO"),("OP","PX")]
    places_90d_r = []
    
    for i in range(5):
        for j in range(5):
            if answer[i] == 0:
                break
            for h_chk in h_check_patterns:
                if h_chk in places[i][j]:
                    answer[i] = 0
                    break
                    
    for i in range(5):
        for j in range(4):
            if answer[i] == 0:
                break
            for k in range(4):
                for b_chk in box_checks_patterns:
                    if places[i][j][k]+places[i][j][k+1] == b_chk[0] and places[i][j+1][k]+places[i][j+1][k+1] == b_chk[1]:
                        answer[i] = 0
                        break
    
    for i in range(5):
        _tmp = []
        for j in range(5):
            if answer[i] == 0:
                break
            _t = ""
            for k in range(5):
                _t += places[i][k][j]
            _tmp.append(_t)
        places_90d_r.append(_tmp)
        
    for i in range(5):
        for j in range(5):
            if answer[i] == 0:
                break
            for h_chk in h_check_patterns:
                if h_chk in places_90d_r[i][j]:
                    answer[i] = 0
                    break
    return answer
    
정확성  테스트
테스트 1 〉	통과 (0.12ms, 10.3MB)
테스트 2 〉	통과 (0.22ms, 10.2MB)
테스트 3 〉	통과 (0.13ms, 10.2MB)
테스트 4 〉	통과 (0.11ms, 10.2MB)
테스트 5 〉	통과 (0.08ms, 10.2MB)
테스트 6 〉	통과 (0.09ms, 10.3MB)
테스트 7 〉	통과 (0.06ms, 10.4MB)
테스트 8 〉	통과 (0.10ms, 10.4MB)
테스트 9 〉	통과 (0.07ms, 10.3MB)
테스트 10 〉	통과 (0.04ms, 10.4MB)
테스트 11 〉	통과 (0.20ms, 10.4MB)
테스트 12 〉	통과 (0.05ms, 10.2MB)
테스트 13 〉	통과 (0.06ms, 10.2MB)
테스트 14 〉	통과 (0.11ms, 10.4MB)
테스트 15 〉	통과 (0.14ms, 10.4MB)
테스트 16 〉	통과 (0.13ms, 10.3MB)
테스트 17 〉	통과 (0.09ms, 10.2MB)
테스트 18 〉	통과 (0.04ms, 10.2MB)
테스트 19 〉	통과 (0.07ms, 10.2MB)
테스트 20 〉	통과 (0.07ms, 10.4MB)