Level 2 거리두기 확인하기 <2021 카카오 인턴십> Python 3

 

최종 코드

• GitHub -> https://github.com/hwayeon351/Programmers-Algorithms/blob/main/level2_거리두기확인하기.py

GitHub - hwayeon351/Programmers-Algorithms: 프로그래머스 알고리즘 소스 코드 모음

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

Level 1 숫자 문자열과 영단어<2021 카카오 인턴십> Python 3

 

• 3. 표 편집 -> https://hwayomingdlog.tistory.com/140

Level 3 표 편집 <2021 카카오 인턴십> Python 3

• 4. 미로 탈출 -> 
• 5. 시험장 나누기 ->