오늘은 프로그래머스의 2021 카카오 채용연계형 인턴십 코딩테스트 문제인 거리두기 확인하기 를 풀어보았다.
1. 문제 설명
개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
1-1. 제한 사항
- places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다. - places의 열 길이(대기실 세로 길이) = 5
- places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다. - 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
- return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
1-2. 입출력 예
2. 나의 풀이
def solution(places):
answer = [1 for i,j in enumerate(places)]
print(answer)
for num, room in enumerate(places):
find_P = []
for i in range(5):
index = -1
while True:
index = room[i].find('P', index + 1)
if index == -1:
break
find_P.append([i, index])
#print(find_P)
for i in range(len(find_P)):
for j in range(i+1,len(find_P)):
#print(find_P[i], find_P[j])
if (abs(find_P[i][0] - find_P[j][0]) + abs(find_P[i][1] - find_P[j][1])) > 2:
continue
elif (abs(find_P[i][0] - find_P[j][0]) + abs(find_P[i][1] - find_P[j][1])) == 1:
answer[num] = 0
break
elif (abs(find_P[i][0] - find_P[j][0]) + abs(find_P[i][1] - find_P[j][1])) == 2:
row1, row2, col1, col2 = find_P[i][0], find_P[j][0], find_P[i][1], find_P[j][1]
if row1 != row2 and col1 != col2:
if room[row1][col2] != 'X' or room[row2][col1] != 'X':
answer[num] = 0
break
elif row1 == row2:
if room[row1][(col1+col2)//2] != 'X':
answer[num] = 0
break
elif col1 == col2:
if room[(row1 + row2)//2][col1] != 'X':
answer[num] = 0
break
return answerㅋㅋㅋ레벨 2 맞나...? 알고리즘 순서는 간단하다.
1. P의 index를 찾고 find_P에 저장해준 뒤
2. 각각에 대해 P의 index에서 맨해튼 거리를 계산한 후 예외사항들 처리
푸는데 오래걸리고 예외사항 생각할게 많았는데 깔끔한 풀이는 아니지만 풀어내기는 했다. 배열이 5X5이므로 하나씩 살펴주는 방식을 택했다.
3. 다른 풀이
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]enumerate를 두번 사용해서 row와 col을 표현한 것이 좋았다. 모든 예외사항을 하나씩 살펴주며 비슷하게 풀어갔지만 직관적이고 풀이가 깔끔하다.
아무튼
레벨 2 문제라고 하는데...배열을 다루는 것이 꽤나 까다로웠다. 그래도 생각한대로 구현해보는 좋은 경험이 되었다. 다음엔 같은 카카오 코테의 표 편집 문제를 풀어봐야겠다.
