[2022 삼성 코딩테스트 상반기 오전 2번] 코드트리 - 팩맨 파이썬 리뷰
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
와오....
무려 이문제는 타이머를 4시간 재고 풀었는데
가닥은 2시간만에 잡혔지만 TC케이스를 전부 통과하기까지는 3시간45분이 걸렸다...
(( 마감 15분전에 다 풀게 된경우?? ))
만약 실전에서 이렇게 됐다면... 사실 어느정도 엣지케이스를 통과할수있게 코드트리가 만들어놔서 다행이지
삼성 현장에서는 TC10번만 통과되고 뒤에있는 약 25번?까지의 엣지케이스에 통과하지 못한다면..
눈으로는 풀었어도 실제로는 통과할 수 없게 되어버린다.
주변에 IT 4대기업 다니고있는 현업엔지니어에게 이문제를 보여줬는데
그친구는 푸는데 4시간이 넘게 걸렸다 ㅋㅋㅋ ( 그래도 코테안한지 1년반이 넘었는데 풀긴 푸는 역시 현업자 클라스.. )
이문제를 풀면서 크게 자료구조를 어떻게 할까 고민이 많았다.
왜냐하면 입력형식중에
- 턴이 진행되는 동안 살아있는 몬스터의 수가 100만개가 넘는 입력은 주어지지 않는다고 가정해도 좋습니다.
라는 부분이 있다. 그말은, 내가 만약 몬스터수를 어떤 배열에 저장한다면 배열의 크기가 최대 100만개 까지도 갈수 있다는 의미니까 배열을 하나하나 탐방하게 하는 방식은 굉장히 비효율 적일 수도있고, 오히려 100번? 정도는 접근해도 괜찮다는 의미라고 생각했다.
그래서 뭔가 쎄~ 함을 감지한 상태로 풀었다. ( 만약 문제가 생기면 이부분을 수정 하기 위해.. )
일단 이문제를 풀며
막혔던 부분을 정리해보자면,
1. 몬스터의 개수를 어떻게 처리할 것인가?
( 처음에는 배열끼리 비교했다가 나중에 3차원 배열로 바꿨다. )
2. 다중 포문을 사용할때 만약 다중 경우의 수를 탐색할때 어떻게 해야 더 효과 적인지
( 깊은카피, 얉은카피의 차이점이 존재한다. - 2차원배열을 가져올때 얇은 카피에서 에러가 발생!!!! )
( 이건 코드트리 선생님에게 한번 물어보고 싶다. 이것도 func 사용하는 것 같은데)
3. 2턴 동안 존재하는 ?? < 국어 문제. 이걸 좀더 안틀리게 처리하기 위해선?
4. 배열끼리 비교해서 어떻게 안전하게 값이 같을때 해당 배열을 지우는지
(이건 뭔가더 좋은처리가 있을까? 역시나 함수화를 해야하나 생각한다..)
5. 팩맨 이동경로는 어떻게 ?
1. 몬스터의 개수를 어떻게 처리할 것인가?
( 처음에는 배열끼리 비교했다가 나중에 3차원 배열로 바꿨다. )
이부분은. 처음엔 monster_arr 라는 배열에 몬스터를 전부다 저장하고, 다시 가져오고
그리고 팩맨의 이동경로가 (0,1) (1,1) (2,1) 이 나온다면, (0,1) 이 monster_arr에 있나 for문으로 하나하나 다 확인하고,
있는경우 그 index를 pop 해서 다 지워 주게 했는데................
미친 시간이 걸릴 수 밖에 없었다.
그도 그럴것이 ( (팩맨 이동경로 3개 + @) x 몬스터수100만 ) * test 케이스 라고하자.
테스트케이스x팩맨이동경로
+@ 가 100만 넘어도 바로 시간초과가 나버리는것이다..
그래서 이 문제는 생각외로 TC28번? 쯤에서 시간초과로 알게 되었는데,
4x4 배열이라는것, 100만까지 주어지는 점을 봐서
이건 몬스터 개수를 하나하나 다 참고하지말고 ,
3차원 배열에 전부다 쑤셔넣은다음 그 3차원 배열을 탐색해야겠다고 생각했다.
만약에 이동경로에 몬스터수가 3개,4개,3개 라면 10번만 탐색하면되는것이니깐.
그래서 3차원배열 [ [ []*n for in range(n)] for _ in range(n) ] 으로 만들어줬다.
그리고 monster_arr 에 있는걸 3차원 배열에 전부 올려서 반영해주는 monster_3d_update() 함수도 만들어서 관리해줬다.
참고로 해당칸에 몬스터가 몇마리있는지를 나타내는 함수도 있었기에 이부분에서 시간이 더 줄었다.
해당 칸에 몬스터가 몇마리 있는지를 표시하는것도 monster_arr를 하나하나 다빼와서 봤기 때문...
그냥 i,j 다 순행 하면 바로 알수있었다.
아! 3차원 배열을 써야하는구나! 했던 부분.
왜냐하면, 3차원배열을 쓰면 여태껏 알고리즘이 깔끔했던 적이 없엇다.
특히나 3차원배열을 사용한 회전이라던지, (해당부분에 여러명의 사람이잇고 이걸 돌린다고 친다면?? )
이부분을 처리하기 굉장히 까다로워서 웬만하면 배열로 접근하려고 했는데 이런 시간초과 문제가 나버렸다.
사용해야할때는 과감히 사용하자. 특히 4x4 밖에 안되는 경우에는 !!
2. 다중 포문을 사용할때 만약 다중 경우의 수를 탐색할때 어떻게 해야 더 효과 적인지
( 깊은카피, 얉은카피의 차이점이 존재한다. - 2차원배열을 가져올때 얇은 카피에서 에러가 발생!!!! )
( 이건 코드트리 선생님에게 한번 물어보고 싶다. 이것도 func 사용하는 것 같은데)
이부분은 사실 함수화를 하는게 좋을거같은데 해설의 경우는
i,j,k = 1,0,1 이런식으로 받고
arr[1,0,1]
for dx1 in arr:
nx,ny = x+dxs[dx1],y+dys[dx1]
이런식으로 해서 체크하고,
v_pos 의 이미 체크했던 배열안에 nx,ny가 없으면 v_pos 배열에 넣고 아니면 그 위치의 점수 계산안하게 해서
점수위치를 return 했다. 와..진짜 이걸 어떻게 생각해내지 그다음에 다음 j 로 이동할수있도록
x,y = nx,ny 로 갱신해주는...
이걸 어떻게 떠올릴수있을까
나는 이걸못해서 하나하나 다 불러오다가.. 방문했던 배열을 다시 deepcopy 해줘야 했고.. 이거 떠올리느라 진짜 시간낭비를 너무했다..
다음엔 이런경우를 함수화 해보는 버릇을 들여보자.
만약에 for 문 다할꺼면 또 방문 배열어떻게 처리할지, 변수는어떻게 할껀지 꼭 유의해서 작성하도록. (에러가많이난다.)
3. 2턴 동안 존재하는 ?? < 국어 문제. 이걸 좀더 안틀리게 처리하기 위해선?
이부분은 문제를 푼 친구가 알려줬는데,
숫자 2 이렇게 하고 -1씩해서 0 될때까지 해서 남기지말고, 현재 라운드 수를 가져온다.
현재 라운드가 1이라면, 2턴동안 존재하면 2,3 턴 존재했으니 4턴에서 없어지겠지.
그래서 만약 현재 라운드 - 적혀있는 라운드 > 2 라면 읽어들이지 않게 처리한다면, 가능할꺼같다.
이런 문제는 문제를 많이풀면 친구가 많이 접해서 테스트케이스를 위주로 처리한다고했다.
나는 이걸 위같이 처리하다가.. tc통과가 안되길래 혹시몰라 숫자를 3으로 넣고하니까 통과됐다..
tc를 사용하는게 좋겠다.
4. 배열끼리 비교해서 어떻게 안전하게 값이 같을때 해당 배열을 지우는지
(이건 뭔가더 좋은처리가 있을까? 역시나 함수화를 해야하나 생각한다..)
괜히 a,b 배열을 비교하면서 b 를 바로 pop 해서 빼버리면, 나중에 문제가 발생한다.
인덱스 0 다음에 1을 읽다가 b의 요소가 변해버려서 인덱스1이 사실은 빼기전 배열 b의 인덱스 2번을 가르키기 때문..
그래서 temp_b같은걸 사용했엇는데 그래도 뭔가 잘안됐다.. (주석처리된부분을 보면알듯)
---- 해결법 ----
1. 배열끼리 비교하는데 b' 를 써서 index값 저장시켜두고 index일때 값을 안가져오게 한다음 b=b' 하면된다.
배열끼리 값을 비교하다가 a배열에있는 값이 b배열에있을때 그걸 빼주려고한다.
a=[a,b,c]
2. Hashmap 사용 - 시간복잡도 더 줄이기 가능
이건 친구가 알려준건데
비교하기 위한 값을 {} 로 선언 하고, key:value 로 설정해주면 불러들일때 O(1) 이 걸리게된다.
a = { 1:True, 2:True, 3:True }
b = [2,3,4] 라면,
for idx,i in enumerate(b) :
if a[i] :
b'.append(idx)
이렇게 해두고
나중에 읽어올때
temp_b = []
for i in range(len(b)):
if not i in b' : # 만약에 이 인덱스가 b'에 있으면 넣으면 안된다.
temp_b.append(b[i])
b = temp_b.copy()
#만약에 b가 2차원배열이면 copy.deepcopy(temp_b) 로 써야한다.
5. 팩맨 이동경로는 어떻게 ?
팩맨 이동경로는 그냥 단순한게 64개를 전부다 탐색하고 탐색경로를 정렬했다.
해설도 보니 그렇게 했고, 이걸 dfs로 하나하나 해볼까했엇는데 탐색경로가 in_range()해서 범위밖으로 안나가게 까지 고려하면 얼마 안될꺼같아서 그냥 전부다 실행했다.
조금 잘안되던부분이있었는데
그게 2번에서 난 오류때문에 계속 경로가 상우하 가 나와야하는데 우상좌 이렇게 나오던 문제였다.
결국 3중포문의 알고리즘 문제였고 이를 해결하니 잘됐다.
마지막으로 기억나는건,
1차원 배열의 경우 copy() 로 해도 독립적으로 배열값을 바꿀 수있다.
하지만, 2차원배열의 경우, 2차원배열안의 배열값을 바꾸면 이는 a도 b도 영향을 받게 되어서, deepcopy 로 해줘야한다.
이걸 파이썬에서 하려면 copy 를 사용해야하고, 이 모듈을 못쓰면 수제로 하나하나 다시 배열을 선언해줘야할수도있다.
그래도 코테보기전에 이걸 알아서 천만 다행이다.
1차 배열은 a = b.copy() 로 깔끔히 사용가능.
2차 배열은 import copy 모듈 사용해서 a = copy.deepcopy(b)
로 해줘야하는것.
그리고 배열값끼리 비교하는방법 등 .
많은걸 알게된 문제였다.
|
import sys
import copy
sys.stdin = open("팩맨.txt",'r')
m,t=map(int,input().split())
r1,c1 = map(int,input().split())
r1-=1
c1-=1
dxs=[-1,-1,0,1,1,1,0,-1]
dys=[0,-1,-1,-1,0,1,1,1]
#격자는 4x4로 정해져있음
n = 4
#배열
#몬스터 복제 (알) 현재 몬스터와 동일한 형태
copy_monster = []
#몬스터의 정보값을 가지는 배열
monster_arr= []
#몬스터들을 3d배열로 관리하는 경우.
monster_3d_arr = [ [[]*n for _ in range(n)] for _ in range(n)]
#몬스터의 개수를 담는 2차원 배열
monster_cnt = [ [0]*n for _ in range(n)]
#팩맨 위치
pacman_arr = [ [False]*n for _ in range(n)]
pacman_arr[r1][c1] = True
#몬스터 시체를 나타내는 2차원 배열
monster_body_arr = [ [0]*n for _ in range(n)]
for _ in range(m) :
r,c,d=map(int,input().split())
r-=1
c-=1
d-=1
monster_arr.append((r,c,d))
def in_range(x,y) :
return 0<=x<n and 0<=y <n
# 몬스터 알까기
def pacman_update() :
global pacman_arr,r1,c1
pacman_arr= [ [False]*n for _ in range(n)]
pacman_arr[r1][c1] = True
return
def monster_copy():
update_3d_monster_arr()
#현재 몬스터 상태를 그대로 가진 몬스터를 만든다.
for i in range(n) :
for j in range(n):
for d in monster_3d_arr[i][j]:
copy_monster.append((i,j,d))
return
def update_3d_monster_arr() :
global monster_3d_arr
monster_3d_arr = [ [[]*n for _ in range(n)] for _ in range(n)]
for r,c,d in monster_arr :
monster_3d_arr[r][c].append(d)
return
def update_monster_arr() :
#얘는 배열값을 표시하기만 할뿐. 쓸모없음.
global monster_arr
global monster_cnt
#monster_cnt 가 2차원 배열이다.
monster_cnt = [ [0]*n for _ in range(n)]
for i in range(n):
for j in range(n):
monster_cnt[i][j] = len(monster_3d_arr[i][j])
return
def move_check(r,c,d) :
for num in range(8):
direction = (d+num)%8
nx,ny=r+dxs[direction],c+dys[direction]
if in_range(nx,ny) and pacman_arr[nx][ny] == False and monster_body_arr[nx][ny] == 0 :
return ((nx,ny,direction))
#만약 한곳도 가지못하면
return (r,c,d)
def monster_move():
global monster_arr
#움직이려는칸에 시체, 팩맨,벗어나면
#반시계방향으로 45도씩 회전하는데, 8방향다돌앗는데 못가면 그냥 가만히있기
#중복해서 한칸에 여러명 가능
temp_arr = []
#각 배열값을 다 순회한다 <
for idx,(r,c,d) in enumerate(monster_arr):
(nr,nc,nd) = move_check(r,c,d)
temp_arr.append((nr,nc,nd))
#8방향 다돌았으면 그냥 끝.
monster_arr= temp_arr.copy()
update_3d_monster_arr()
update_monster_arr()
return
def pacman_move():
global monster_cnt, monster_arr,r1,c1
#상좌 하우의 우선순위를 가지고
#3칸을 이동하는데. 몬스터를 가장 많이 먹을 수 있는 경우의 수다.
#이동칸에 몬스터를 다 먹어치우고 시체를 남긴다.
#알은안먹음. 움직이기전에 같은 칸에있는 몬스터 안먹고, 이동하는 과정중만 먹는다.
#팩맨이잇는자리에 알이 태어날경우를 말하는듯.
dx=[-1,0,1,0]
dy=[0,-1,0,1]
x,y=r1,c1 # r1,c1이 팩맨의 위치다.
where_is_64_pac_go = []
moving = []
for i in range(4):
#이거 , 얉은 복사때문에 monster_cnt값이 자꾸 영향을 받는다...왜냐하면 배열안의 다른 리스트는 주소값이 같아서 나는문제.
#이거 처리하는거 무조껀 코드트리 선생님한테 질문하기 . 이거 변수 처리하다가 진심 머리 터지는줄알앗다.
# 끝부분에서 점수포인트를 0으로 초기화하니까 얘네들이 끝까지 가면 점수가 다 날아가버려서 중간중간에 백업을 해줘야했음.
temp_monster_cnt = copy.deepcopy(monster_cnt)
monster_howmany1 = 0
nx1,ny1 = x+dx[i],y+dy[i]
delete1 = [ [False] * n for _ in range(n)]
if in_range(nx1,ny1) :
moving.append((nx1,ny1))
if not delete1[nx1][ny1] :
monster_howmany1 += temp_monster_cnt[nx1][ny1]
delete1[nx1][ny1] = True
for j in range(4) :
nx2,ny2 = nx1+dx[j],ny1+dy[j]
delete2 = copy.deepcopy(delete1)
monster_howmany2 = monster_howmany1
if in_range(nx2,ny2):
moving.append((nx2,ny2))
if not delete2[nx2][ny2] :
monster_howmany2 += temp_monster_cnt[nx2][ny2]
delete2[nx2][ny2] = True
for z in range(4) :
nx3,ny3=nx2+dx[z],ny2+dy[z]
delete3 = copy.deepcopy(delete2)
monster_howmany3 = monster_howmany2
if in_range(nx3,ny3) :
moving.append((nx3,ny3))
if not delete3[nx3][ny3] :
monster_howmany3 += temp_monster_cnt[nx3][ny3]
delete3[nx3][ny3] = True
temp_moving = copy.deepcopy(moving)
where_is_64_pac_go.append((monster_howmany3,i,j,z,temp_moving,nx3,ny3)) #이미 여기서 상하좌우 순서대로 가져갈꺼다.
moving.pop() # 갱신을위해 빼버리기
temp_monster_cnt = copy.deepcopy(monster_cnt)
moving.pop()
moving.pop()
#print(where_is_64_pac_go)
where_is_64_pac_go.sort(key=lambda x:(-x[0],x[1],x[2],x[3]))
# 몬스터 먹은개수, 처음이동, 2번째 이동, 3번째이동, 각 경로를 담은 배열
#이게 과연 좌우상하를 가지고 됐을까?
eat,first,second,third,moving_arr,last_x,last_y = where_is_64_pac_go[0]
#팩맨위치 갱신
r1,c1 = last_x,last_y
pacman_update()
#여기서 경로상에 있는 몬스터들 다 지우고, 그녀석들만큼 시체에 넣는다.
#이거 배열끼리 비교해서 어떻게 안전하게 값 같을때 해당 배열 지우는지 블로그 글쓰기 <<<<<<<<<<<<<<
#몬스터들 잡아먹히고 난다음 갱신, 시체 갱신
for item in moving_arr:
q,p = item
#안에있는놈 다 날려버리기.
if len(monster_3d_arr[q][p] ) > 0 :
monster_3d_arr[q][p] = []
monster_body_arr[q][p] = 3
#초기화 하고 다시 넣어준다.
monster_arr= []
for i in range(n) :
for j in range(n) :
if len(monster_3d_arr[i][j]) > 0 :
for item in monster_3d_arr[i][j] :
monster_arr.append((i,j,item))
"""
for item in moving_arr:
q,p = item
for (q1,p1,dir1) in (monster_arr):
if q==q1 and p == p1 : #해당하는 위치에 똑같은값들이 있다면,
monster_body_arr[q1][p1] = 3 #두턴이 3인? ㅋㅋ
if not (q,p,dir1) in temp_monster_arr : continue
idx = temp_monster_arr.index((q1,p1,dir1))
temp_monster_arr.pop(idx) #그 값을 빼버린다.
#그 장소에 시체를 2턴간 남긴다.
continue
monster_arr = temp_monster_arr.copy()
"""
return
def monster_body_disapear():
global monster_body_arr
#몬스터 시체가 2턴만 유지된다.
for i in range(n):
for j in range(n) :
if monster_body_arr[i][j] > 0 :
monster_body_arr[i][j] -= 1
#전부다 하나씩 감소
return
def monster_copy_complete():
global copy_monster,monster_arr
#알형태인 몬스터가 부화한다.
for (i,j,d) in copy_monster :
monster_arr.append((i,j,d))
copy_monster = []
return
def cal_monster_():
return len(monster_arr)
#모든턴 진행 뒤 살아남은 몬스터의 마리수
for tc in range(t) :
monster_copy()
monster_move()
pacman_move()
monster_body_disapear()
monster_copy_complete()
print(cal_monster_())
|