문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 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을 담습니다.
입출력 예
| 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초
- 두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다.
나의 풀이
[Python(파이썬)]
def solution(places):
answer = []
for i in places:
checkclass = i
forbreak = True
for j in range(5):
for k in range(5):
if checkclass[j][k] == 'P':
if k < 4: # 맨해튼 1,2인 옆
if checkclass[j][k + 1] == 'P':
forbreak = False
break
if k < 3 and checkclass[j][k+2] == 'P':
if checkclass[j][k+1] != 'X':
forbreak = False
break
if j < 4: # 맨해튼 1,2인 뒤
if checkclass[j+1][k] == 'P':
forbreak = False
break
if j < 3 and checkclass[j+2][k] == 'P':
if checkclass[j+1][k] != 'X':
forbreak = False
break
# 맨해튼 = 2 대각선 검사
if k != 4 and j != 4: # 맨해튼 = 2 대각선 검사
if checkclass[j+1][k+1] == 'P':
if checkclass[j][k+1] == 'O' or checkclass[j+1][k] == 'O':
forbreak = False
break
if k != 0 and j != 4:
if checkclass[j+1][k-1] == 'P':
if checkclass[j][k-1] == 'O' or checkclass[j+1][k] == 'O':
forbreak = False
break
if forbreak == False:
break
if forbreak == True:
answer.append(1)
else:
answer.append(0)
return answer
학습한 내용
※ 이 문제에서 생각해야 할 것
- 응시자가 앉아있는 자리 ( P ), 빈 테이블 ( O ), 파티션 ( X ) -> places 원소는 P, O, X로 이루어져있음
- 거리두기를 지키고 있으면 -> 배열에 1 , 한 명이라도 지키지 않으면 배열에 0 담기
- 출력 값은 1차원 정수 리스트에 5개의 원소
풀이과정
1. 거리두기 옆자리 검사 (맨해튼 = 1 or 2)
2. 거리두기 뒷자리 검사 (맨해튼 = 1 or 2)
3. 거리두기 대각선 검사
3. 다른 방법
1. 거리두기 옆자리 검사 (맨해튼 = 1 or 2)
for문을 돌렸을 때 인덱스를 넘어가는 IndexError: string index out of range 에러가 나올 수 있으니 조심해야 한다.
맨해튼 1인 경우 k < 4까지만 검사하고 맨해튼 2인 경우 k < 3까지만 검사해야한다.
if k < 4: # 맨해튼 1,2인 옆
if checkclass[j][k + 1] == 'P':
forbreak = False
break
if k < 3 and checkclass[j][k+2] == 'P':
if checkclass[j][k+1] != 'X':
forbreak = False
break
2. 거리두기 뒷자리 검사 (맨해튼 = 1 or 2)
뒷자리 검사할때도 IndexError: string index out of range 에러를 조심해야한다.
맨해튼 1인 경우 j < 4까지만 검사하고 맨해튼 2인 경우 j < 3까지만 검사해야한다.
if j < 4: # 맨해튼 1,2인 뒤
if checkclass[j+1][k] == 'P':
forbreak = False
break
if j < 3 and checkclass[j+2][k] == 'P':
if checkclass[j+1][k] != 'X':
forbreak = False
break
※ 보라색 화살표를 잊지 않아야 한다.
보라색 화살표에서 제일 오른쪽줄은 옆은 하지말고 뒤만, 제일 뒷줄은 뒤는 하지말고 앞만 검사를 했어야하는데 제일 오른쪽줄, 뒷줄을 다 하지 말아야하는 줄 아고 리스트 인덱스를 가리키는 for문 변수인 j, k가 3 미만 인 경우에만 맨해튼 = 2인 경우를 검사했다.
이 문제가 나온지 얼마 안돼서 테스트 케이스도 없어서 한참 해맸다ㅠㅠ
3. 거리두기 대각선 검사
왼쪽 그림은 오른쪽 대각선을 검사하는 경우이다.
제일 오른쪽 줄(k=4), 제일 뒷줄(j=4)인 경우에 오른쪽 대각선을 검사하면 index error가 발생하기 때문에 제외시켜야한다.
그다음 오른쪽 그림은 왼쪽 대각선을 검사하는 경우이다.
제일 왼쪽 줄(k=0), 제일 뒷줄(j=4)인 경우에 왼쪽 대각선을 검사하면 index error가 발생하기 때문에 제외시켜야한다.
카카오에서 제공된 해설을 보니 이 문제는 사람이 있는 정점에서 거리 2 이내에 다른 사람이 있는 정점이 있는지를 검사하는 그래프 탐색문제라고 되어있었다.
따라서 사람들이 있는 정점들에서 시작하는 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)알고리즘을 사용하는 방법이 있고 이 방법 이외에 내가 풀이한 방법인 이중 반복문을 사용하여 직접 한칸씩 확인하는 방법도 있었다.
2021 카카오 인턴십 for Tech developers 코딩 테스트 해설
2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테스트가 지난 2021년 5월 8일에 4시간에 걸쳐 진행되었습니다. 이번 인턴 코딩 테스트에서는 5문제가 출제되었습니다. 이전과 동일하게 쉬운
tech.kakao.com
문제 출처
코딩테스트 연습 - 거리두기 확인하기
[["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]
programmers.co.kr
'[Python] Programmers > Level2' 카테고리의 다른 글
| [프로그래머스/Level2] 메뉴 리뉴얼 (2021 카카오 신입공채) (0) | 2021.07.26 |
|---|---|
| [프로그래머스/Level2] 전화번호 목록 (0) | 2021.07.23 |
| [프로그래머스/Level2] 수식 최대화 (2020 카카오 인턴십) (0) | 2021.07.21 |
| [프로그래머스/Level2] 괄호 변환 (2020 카카오 블라인드) (0) | 2021.07.20 |
| [프로그래머스/Level2] 프린터 (0) | 2021.07.19 |
댓글