최종 코드
def solution(places):
m1_x = [-1, 0, 1, 0]
m1_y = [0, -1, 0, 1]
m2_x = [0, -1, 1, -2, 2, -1, 1, 0]
m2_y = [-2, -1, -1, 0, 0, 1, 1, 2]
px = [[0], [0,-1], [0,1], [-1], [1], [-1,0], [1,0], [0]]
py = [[-1], [-1,0], [-1,0], [0], [0], [0,1], [0,1], [1]]
answer = []
for room in places:
check = True
for y in range(5):
for x in range(5):
if room[y][x] == 'P':
#맨해튼 거리 1
for dx, dy in zip(m1_x, m1_y):
nx = x+dx
ny = y+dy
if 0 <= nx < 5 and 0 <= ny < 5:
if room[ny][nx] == 'P':
check = False
break
else:
#맨해튼 거리 2
for d in range(len(m2_x)):
nx = x+m2_x[d]
ny = y+m2_y[d]
if 0 <= nx < 5 and 0 <= ny < 5:
if room[ny][nx] == 'P':
#파티션 체크
for p in range(len(px[d])):
p_x = x+px[d][p]
p_y = y+py[d][p]
if 0 <= p_x < 5 and 0 <= p_y < 5:
if room[p_y][p_x] != 'X':
check = False
break
else: continue
else: continue
if check: answer.append(1)
else: answer.append(0)
return answer
풀이 과정
풀이 시간 43분
응시자가 있는 위치로부터 맨해튼거리가 2이하인 곳에 다른 응시자가 있는 경우가 하나라도 발생하면, 거리두기를 지키지 않은 대기실이다.
따라서, 각 대기실에서 응시자가 있는 위치를 기준으로 다음 두 가지를 체크해줬다.
1. 맨해튼거리가 1인 위치에 다른 응시자가 없는지 살핀다.
-> 다른 응시자가 있는 경우, 거리두기 실패 대기실이므로 현재 대기실 탐색을 종료하고 다음 대기실을 탐색한다
2. 맨해튼 거리가 2인 위치에 다른 응시자가 있는 경우, 파티션이 잘 설치되어 있는지 확인한다
-> 파티션이 잘 설치되어 있지 않은 경우, 거리두기 실패 대기실이므로 현재 대기실 탐색을 종료하고 다음 대기실을 탐색한다.
모든 응시자가 위 두가지 조건을 탐색하여 모두 거리두기가 준수한 경우가 거리두기를 지킨 대기실이 된다.
위의 로직을 구현하기 위해 먼저, m1_x, m1_y, m2_x, m2_y, px, py 리스트를 선언해줬다.
현재 체크하고자 하는 응시자의 위치가 (x, y)인 경우, 각각이 의미하는 바는 다음과 같다.
1. 맨해튼 거리 1인 위치 = (x+m1_x[i], y+m1_y[i])
2. 맨해튼 거리 2인 위치 = (x+m2_x[i], y+m1_y[2])
3. 맨해튼 거리 2인 위치와 응시자의 위치 사이의 파티션이 필요한 위치 = (x+px[i][j], y+py[i][j])
이 때, len(m1_x) = len(m1_y) = 4, len(m2_x) = len(m2_y) = len(px) = len(py) = 8이다.
따라서, 응시자의 위치가 (x, y)인 경우, 거리두기가 잘 되어있는 응시자인지 판단하기 위해 필요한 최대 연산 횟수는(필요한 파티션 개수가 2인 경우) 4+8*2 = 20번이다.
즉, 대기실은 총 5개이고, 자리는 5*5개가 있으므로, 모든 자리에 응시자가 앉아있다고 가정할 때 최악의 경우를 생각할 수 있다.
대략, 대기실 5 * 응시자 수 25 * 거리두기 체크 20 = 2500번의 연산이 필요하다.
def solution(places):
#(x+m1_x[i], y+m1_y[i]) = (x, y)와의 맨해튼거리가 1인 위치
m1_x = [-1, 0, 1, 0]
m1_y = [0, -1, 0, 1]
#(x+m2_x[i], y+m2_y[i]) = (x, y)와의 맨해튼거리가 2인 위치
m2_x = [0, -1, 1, -2, 2, -1, 1, 0]
m2_y = [-2, -1, -1, 0, 0, 1, 1, 2]
#(x+px[i][j], y+py[i][j]) = (x, y)와 (x+m2_x[i], y+m2_y[i]) 사이의 필요한 파티션 위치
px = [[0], [0,-1], [0,1], [-1], [1], [-1,0], [1,0], [0]]
py = [[-1], [-1,0], [-1,0], [0], [0], [0,1], [0,1], [1]]
answer = []
for room in places:
#거리두기에 성공한 경우 check = True, 실패한 경우 = check = False
check = True
for y in range(5):
for x in range(5):
#(x, y)에 응시자가 있는 경우, 거리두기 여부 탐색
if room[y][x] == 'P':
#1. 맨해튼거리 1에 있는 다른 응시자가 있는지 탐색
for dx, dy in zip(m1_x, m1_y):
nx = x+dx
ny = y+dy
if 0 <= nx < 5 and 0 <= ny < 5:
#맨해튼거리 1에 다른 응시자가 있으므로, 현재 대기실은 거리두기 실패이다
if room[ny][nx] == 'P':
check = False
break
#맨해튼거리 1에 다른 응시자가 없는 경우
else:
#2. 맨해튼 거리 2에 있는 다른 응시자가 있는지 탐색
for d in range(len(m2_x)):
nx = x+m2_x[d]
ny = y+m2_y[d]
if 0 <= nx < 5 and 0 <= ny < 5:
#맨해튼거리 2에 다른 응시자가 있는 경우, 파티션이 올바르게 설치되어 있는지 확인한다
if room[ny][nx] == 'P':
#파티션 체크
for p in range(len(px[d])):
p_x = x+px[d][p]
p_y = y+py[d][p]
if 0 <= p_x < 5 and 0 <= p_y < 5:
#파티션이 필요한 위치에 파티션이 없는 경우, 현재 대기실은 거리두기 실패이다
if room[p_y][p_x] != 'X':
check = False
break
else: continue
else: continue
#거리두기에 성공한 경우, 1
if check: answer.append(1)
#거리두기에 실패한 경우, 0
else: answer.append(0)
return answer
#시간복잡도 = O(n), 공간복잡도 = O(n)
참고
- 1. 숫자 문자열과 영단어 -> https://hwayomingdlog.tistory.com/134
- 3. 표 편집 -> https://hwayomingdlog.tistory.com/140
- 4. 미로 탈출 ->
- 5. 시험장 나누기 ->
'코테 노트 > 프로그래머스' 카테고리의 다른 글
Level 2 수식 최대화 <2020 카카오 인턴십> Python 3 (0) | 2021.09.02 |
---|---|
Level 3 경주로 건설 <2020 카카오 인턴십> Python 3 (0) | 2021.09.01 |
Level 3 불량 사용자 <2019 카카오 인턴십> Python 3 (0) | 2021.08.31 |
Level 1 크레인 인형뽑기 게임 <2019 카카오 인턴> Python 3 (0) | 2021.08.30 |
Level 3 표 편집 <2021 카카오 인턴십> Python 3 (0) | 2021.08.27 |