문제
https://programmers.co.kr/learn/courses/30/lessons/81302
코딩테스트 연습 - 거리두기 확인하기
[["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
풀이
처음엔 반복문을 돌며 기준 좌표 P를 찾았다.
기준 좌표에서 맨해튼 2 이하의 다른 P위치를 찾고 그것과 기준 좌표 사이가 O로 되어있는지, 로 되어있는지 확인하여
거리두기를 위반했는지 아닌지를 판단하려 했다.
def solution(places):
answer = []
for p in places:
for i in range(len(p)):
p[i] = list(p[i])
print(places)
coord = [(-2, 0),
(-1, -1), (-1, 0), (-1, 1),
(0, -2), (0, -1), (0, 1), (0, 2),
(1, -1), (1, 0), (1, 1),
(2, 0)]
for p in places:
for y in range(5):
for x in range(5):
if p[y][x] == 'P':
pCoord = []
#P의 맨해튼 거리 2 이하에 위치한 또다른 P의 좌표 저장
for c in coord:
if c[0]+y >= 0 and c[0]+y < 5 and c[1]+x >= 0 and c[1]+x < 5:
if p[y+c[0]][x+c[1]] == 'P':
pCoord.append(c)
#for c in pCoord:
# for _y in range(c[0]):
# print(_y)
for i in range(-1, -1, -1):
print(i)
return answer그런데 풀면서 이건 아닌 것 같다는 예감이 들었다
너무 복잡해짐..
그래서 해설을 봤다. 참고로 코드는 제공되지 않고 아이디어만 적혀있다.
2021 카카오 인턴십 for Tech developers 코딩 테스트 해설
2021년 카카오의 여름 인턴십의 첫 번째 관문인 코딩 테스트가 지난 2021년 5월 8일에 4시간에 걸쳐 진행되었습니다. 이번 인턴 코딩 테스트에서는 5문제가 출제되었습니다. 이전과 동일하게 쉬운
tech.kakao.com
앗 BFS/DFS 이었군
그래서 기준 좌표에서 상하좌우좌표에 P가 있다면 거리두기 위반, O가 있다면 스택에 좌표를 넣고
그 좌표를 기준으로 P가 있는지 확인하였다.
다만 기준 좌표 P도 상하좌우중 한 곳에 있을 것이므로 P가 2개 이상이면 위반이라고 판단하였다.
def solution(places):
answer = []
for p in places:
for i in range(len(p)):
p[i] = list(p[i])
coord = [(-1, 0), (0, -1), (0, 1), (1, 0)]
for p in places:
isFinished = False
for y in range(5):
for x in range(5):
if p[y][x] == 'P': #기준 좌표
stack = []
for c in coord:
if c[0]+y >= 0 and c[0]+y < 5 and c[1]+x >= 0 and c[1]+x < 5:
if p[y+c[0]][x+c[1]] == 'P': #상하좌우에 P가 있을 경우
answer.append(0)
isFinished = True
break
if p[y+c[0]][x+c[1]] == 'O': #빈 테이블이 있을 경우 DFS 스택에 추가
stack.append((y+c[0],x+c[1]))
if isFinished:
break
for y1, x1 in stack:
pNum = 0
for c in coord:
if c[0]+y1 >= 0 and c[0]+y1 < 5 and c[1]+x1 >= 0 and c[1]+x1 < 5:
if p[y1+c[0]][x1+c[1]] == 'P': #기준 좌표 제외 P가 2개 이상일 경우 거리두기 위반
pNum += 1
if pNum > 1:
answer.append(0)
isFinished = True
break
if isFinished:
break
if isFinished:
break
if isFinished:
break
if not isFinished:
answer.append(1)
return answer
어찌어찌 통과는 했는데 현타온다 ..
기존 코드를 재사용하면서 의식의 흐름대로 덧붙이다보니 더 더러워졌다.
깔끔하게 바꿔봐야겠다.
다른 사람 코드
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]이사람은 DFS로 푼게 아니고
처음에 내가 풀었던대로 맨해튼 거리 2 이하의 다른 P와 그 사이값을 확인했다.
이게 더 효율적인 코드일 것 같긴 하다.
변수 네이밍이 괜찮은 것 같다.
irow, icol로 해서 row와 구분하여 행 열의 인덱스임이 드러난다. 또 cell이라고 네이밍해서 한 칸임이 잘 드러난 것 같다.
나는 매번 생각나는대로 네이밍하는데, 나중에 문제가 복잡해지면 헷갈려서 규칙을 정해두고 이름지으면 좋을 것 같다.
def solution(places):
result = []
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def f(i, j, cnt):
nonlocal good
if cnt >2 : return
if -1<i<5 and -1<j<5:
if graph[i][j] == 'X':
return
if cnt != 0 and graph[i][j] == 'P':
good = 0
return
graph[i][j] = 'X'
for w in range(4):
ni = i+dx[w]
nj = j+dy[w]
f(ni, nj, cnt+1)
for case in places:
graph = [list(r) for r in case]
good = 1
for i in range(5):
for j in range(5):
if graph[i][j]=='P':
f(i,j,0)
result.append(good)
return result이분은 재귀로 DFS를 구현하신 것 같다.
nonlocal 은 처음 봤다. (https://devbruce.github.io/python/py-13-global,nonlocal/)
함수로 빼지 않은 이유가 flag때문에 복잡해질까봐였는데, nonlocal 을 사용하면 한층 깔끔하게 짤 수 있을 것 같다.