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]