253. 거리두기
1) 어떤 전략(알고리즘)으로 해결?
- 이것도 구현~
2) 코딩 설명
<내 풀이>
< 내 틀렸던 풀이, 문제점>
31개 중 5개 틀린 83.5점 풀이
def solution(places):
answer = [1 for _ in range(len(places))]
idx = 0
for pl in places :
mapp = []
people = []
for ppll in pl :
mapp.append(list(ppll))
for m in range(len(mapp)) :
for mm in range(len(mapp[m])) :
if mapp[m][mm] == "P" :
people.append((m,mm))
# print(people)
for p in range(len(people)) :
if answer[idx]==0 :
break
for pp in range(p+1, len(people)) :
if answer[idx]==0 :
break
if(abs(people[p][0]-people[pp][0])+abs(people[p][1]-people[pp][1]))<3 :
# print(people[p][0],people[pp][0],people[p][1],people[pp][1])
if people[p][0]==people[pp][0] :
if people[p][1]<people[pp][1] :
if 0<=people[p][1]+1<len(mapp) and not mapp[people[p][0]][people[p][1]+1] == 'X' :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and not mapp[people[pp][0]][people[pp][1]+1] == 'X' :
answer[idx] = 0
print(people[p], people[pp])
elif people[p][1]==people[pp][1] :
if people[p][0] < people[pp][0] :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[p][0]+1][people[p][1]] == 'X' :
answer[idx] = 0
else :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[pp][0]+1][people[pp][1]] == 'X' :
answer[idx] = 0
else :
if people[p][0] < people[pp][0] :
if 0<=people[p][1]+1<len(mapp) and 0<=people[pp][1]-1<len(mapp) and not ( mapp[people[p][0]][people[p][1]+1]=='X' and mapp[people[pp][0]][people[pp][1]-1]=='X' ) :
answer[idx] = 0
elif 0<=people[p][1]+1<len(mapp) and not ( mapp[people[p][0]][people[p][1]+1]=='X') :
answer[idx] = 0
elif 0<=people[pp][1]-1<len(mapp) and not (mapp[people[pp][0]][people[pp][1]-1]=='X') :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and 0<=people[p][1]-1<len(mapp) and not ( mapp[people[pp][0]][people[pp][1]+1]=='X' and mapp[people[p][0]][people[p][1]-1]=='X' ) :
answer[idx] = 0
elif 0<=people[pp][1]+1<len(mapp) and not ( mapp[people[pp][0]][people[pp][1]+1]=='X') :
answer[idx] = 0
elif 0<=people[p][1]-1<len(mapp) and not (mapp[people[p][0]][people[p][1]-1]=='X') :
answer[idx] = 0
idx+=1
return answer
print(solution([["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"]]))
def solution(places):
answer = [1 for _ in range(len(places))]
idx = 0
for pl in places :
mapp = []
people = []
for ppll in pl :
mapp.append(list(ppll))
for m in range(len(mapp)) :
for mm in range(len(mapp[m])) :
if mapp[m][mm] == "P" :
people.append((m,mm))
print("map ")
for mmm in mapp:
print(mmm)
for p in range(len(people)) :
if answer[idx]==0 :
break
for pp in range(p+1, len(people)) :
if answer[idx]==0 :
break
print(people[p], people[pp])
if(abs(people[p][0]-people[pp][0])+abs(people[p][1]-people[pp][1]))<3 :
# 2 이하라면 검사 시작
if people[p][0]==people[pp][0] : # 행이 같다라고 한다라면은
if people[p][1]<people[pp][1] :
# 유일하게 행같을 때, 맨해튼 거리 지키는 경우 P-X-P 순서로 앉을 때뿐
if 0<=people[p][1]+1<len(mapp) and not mapp[people[p][0]][people[p][1]+1] == 'X' :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and not mapp[people[pp][0]][people[pp][1]+1] == 'X' :
answer[idx] = 0
##############################################################################################
elif people[p][1]==people[pp][1] : # 열이 같다라고 한다라면은
# P
# X
# P
if people[p][0] < people[pp][0] :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[p][0]+1][people[p][1]] == 'X' :
answer[idx] = 0
else :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[pp][0]+1][people[pp][1]] == 'X' :
answer[idx] = 0
##############################################################################################
# 열이나 행이 같지 않은 대각선
else :
if people[p][0] < people[pp][0] :
if 0<=people[p][1]+1<len(mapp) and 0<=people[pp][1]-1<len(mapp) and not ( mapp[people[p][0]][people[p][1]+1]=='X' and mapp[people[pp][0]][people[pp][1]-1]=='X' ) :
answer[idx] = 0
elif 0<=people[p][1]+1<len(mapp) and not ( mapp[people[p][0]][people[p][1]+1]=='X') :
answer[idx] = 0
elif 0<=people[pp][1]-1<len(mapp) and not (mapp[people[pp][0]][people[pp][1]-1]=='X') :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and 0<=people[p][1]-1<len(mapp) and not ( mapp[people[pp][0]][people[pp][1]+1]=='X' and mapp[people[p][0]][people[p][1]-1]=='X' ) :
answer[idx] = 0
elif 0<=people[pp][1]+1<len(mapp) and not ( mapp[people[pp][0]][people[pp][1]+1]=='X') :
answer[idx] = 0
elif 0<=people[p][1]-1<len(mapp) and not (mapp[people[p][0]][people[p][1]-1]=='X') :
answer[idx] = 0
idx+=1
return answer
print(solution([["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"]]))87 점 풀이
- 5 11 13 31 통과 안됨
def solution(places):
answer = [1 for _ in range(len(places))]
idx = 0
for pl in places :
mapp = []
people = []
for ppll in pl :
mapp.append(list(ppll))
for m in range(len(mapp)) :
for mm in range(len(mapp[m])) :
if mapp[m][mm] == "P" :
people.append((m,mm))
print("map ")
for mmm in mapp:
print(mmm)
for p in range(len(people)) :
if answer[idx]==0 :
break
for pp in range(p+1, len(people)) :
if answer[idx]==0 :
break
print(people[p], people[pp])
if(abs(people[p][0]-people[pp][0])+abs(people[p][1]-people[pp][1]))<3 :
# 2 이하라면 검사 시작
if people[p][0]==people[pp][0] : # 행이 같다라고 한다라면은
if people[p][1]<people[pp][1] :
# 유일하게 행같을 때, 맨해튼 거리 지키는 경우 P-X-P 순서로 앉을 때뿐
if 0<=people[p][1]+1<len(mapp) and not mapp[people[p][0]][people[p][1]+1] == 'X' :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and not mapp[people[pp][0]][people[pp][1]+1] == 'X' :
answer[idx] = 0
##############################################################################################
elif people[p][1]==people[pp][1] : # 열이 같다라고 한다라면은
# P
# X
# P
if people[p][0] < people[pp][0] :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[p][0]+1][people[p][1]] == 'X' :
answer[idx] = 0
else :
if 0<=people[p][0]+1<len(mapp) and not mapp[people[pp][0]+1][people[pp][1]] == 'X' :
answer[idx] = 0
##############################################################################################
# 열이나 행이 같지 않은 대각성
else :
if people[p][0] < people[pp][0] :
if 0<=people[p][1]+1<len(mapp) and 0<=people[pp][1]-1<len(mapp) and not ( mapp[people[p][0]][people[p][1]+1]=='X' and mapp[people[pp][0]][people[pp][1]-1]=='X' ) :
answer[idx] = 0
else :
if 0<=people[pp][1]+1<len(mapp) and 0<=people[p][1]-1<len(mapp) and not ( mapp[people[pp][0]][people[pp][1]+1]=='X' and mapp[people[p][0]][people[p][1]-1]=='X' ) :
answer[idx] = 0
idx+=1
return answer
# print(solution([["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"]]))
print(solution([["PX","XP"]]))TIP
- https://school.programmers.co.kr/questions/27106
문제 풀다가 아무리 생각해도 코드가 너무 지저분하다고 생각되어서 질문하기를 보다가 우연히 이런 조건을 체크해보라고 해서
해봤더니 너무 쉽게 풀리는..... 그래서 다른 분들에게 도움을 드리고자 팁 남깁니다.
문제에서 체크해야 하는 부분은 P를 기준으로 상,하,좌,우 (2칸씩), 대각선(1칸씩)을 체크해서 거리두기(맨해튼거리<=2)가 잘 되고 있는지를 보는건데, P와P 사이에 X(파티션)가 있다면 괜찮고, 대각선의 경우에는 파티션이 2개 설치되어야 하는데 이를 다 체크하려면 매우매우매우 코드가 더러워집니다...
1) O를 기준으로 상하좌우 P가 있는지 체크하자.(2개이상)
2) P를 기준으로 상하좌우 P가 있는지 체크하자.(1개이상)
1)을 하는 이유는 PXP는 가능하지만 POP는 불가능하다. 따라서 O를 기준으로 상하좌우체크를 해주면 커버가 됩니다.
또한 대각선도 이와 유사하게 이렇게 되어있다고 하면 대각선도 체크할 수 있습니다.
O P
P
따라서 2이상인지만 체크하면 됩니다.
2) 조건은 아래와 같은 케이스의 경우때문에 체크를 해주어야합니다. 1의 조건에 따르면 갯수가 각각 1이나오므로...
X P P X
X O O X
X X X X
