코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
코딩테스트 3일전... 그리고 또다른 코테 2일전... 사실 아무생각이없다. ㅋㅋ
그냥 정진하자는 생각으로 부딫힐뿐..
그리고 문제를 읽고 떠올릴수있게 하는 능력.. 과연 체득이 가능할지 모르겠지만
그냥 고민하지 않고 문제만 풀고 정리하는것이 내가 할 수 있는 길이 아닐까..
골드 1문제고 생각외로 1시간 45분? 정도에 다 풀 수 있엇다. 나선형에 달팽이라 뭔가 어렵지 않을가 했는데
come배열 테크닉 ( 이전에 방문한 좌표값 저장 했다가 꺼내오는 ) 을 사용하니깐 생각외로 쉽게 처리 할 수 있었다.
처음에 한번 come 배열을 만들어 놓으면 나중에 계속 쓸 수 있으니 아주 활용 적이였고,
이문제를 풀면서 까다로웠던점은
1. 몬스터들 앞으로 당기기
2. 몬스터들 4마리 이상일때 지우기 (2차원배열에 반영?
3. 몬스터를 총개수,숫자 크기 대로 바꾸고 다시 미로에 넣어서 반영하기
1. 몬스터들 앞으로 당기기
1번의 경우 0,0 을 시작으로 방향 d=0으로 출발해서 배열 이탈 or visited방문이면 방향을 트는 식으로 쭉쭉 나아가며
come 배열에 이전에 왔던 좌표값을 튜플로 저장했다.
그 저장된 come배열을 앞으로 계속쓸꺼니까 return해서 뺴줬다.
그렇게 쭉 돌면서 숫자가 있으면 1차원 deque에 저장한다. (시간아끼기위해)
그리고 n//2,n//2까지도착했으면 종료시키고, 읽어들인 deque을 reverse() 해준다(중요, 그래야 다시 달팽이 바깥으로 나가면서 인덱스 문제없이 넣기 가능.)
그다음 n//2,n//2 의 값을 하나씩 빼면서 해당 인덱스에 해당하는 배열을 불러온다.
그렇게하면 새롭게 몬스터를 앞당길수있다.
2. 몬스터들 4마리 이상일때 지우기 (2차원배열에 반영?
음 처음에는 이거 bfs써서 4마리 이상이면 지우게 하는건줄알았는데..
자세히 보니 격자 같이 생긴 그림에서 잘리는것이였다.
그말은 1차원 리스트를 비교하면서 값을 세다가 4마리 이상이 발견되면,
그녀석들의 인덱스값을 저장해놨다가
새로운 temp배열에 그 인덱스를 제외한 값들을 넣어두게 작성했다.
이건 근데 같은 값들을 읽다가 맨마지막에 예외처리? 하는게 조금 귀찮았다.
여기서 많은시간을 잡아먹었던 기억.
아마 알고리즘 제대로 보면 저런 예외처리없이 깔끔히 할 수 있을꺼같은데 이건기회 될떄 다시
만들어야겠다. ( 배열을 아예 최대 길이로 선언하고 비교하면 저런 예외처리 없이 할수있을듯)
그리고 이녀석들이 안나올때까지의 처리는
함수를 while문 안에 사용하게 하고, 만약 4이상이 하나도없으면 false,_ 를 출력하게 해서
판단했다. 역시 파이썬. return 값을 자유자재로 바꿀 수있는게 너무 편하다(나중에 독이 될지도..)
3. 몬스터를 총개수,숫자 크기 대로 바꾸고 다시 미로에 넣어서 반영하기
이거는 처음에 어떻게 하나 고민좀했는데..
쭉 세다가 값이 달라지면, 지금까지 저장한 숫자,해당숫자크기 를 배열에 넣어주는 재귀함수식? 으로 풀었다.
아 그리고 달라질때 꼭 개수를 1로 초기화 해주는것.
어려워 보였는데 막상 구현하는데는 15분? 정도 밖에 안걸린듯.
문제를 풀수록 중요한건
1. 초기화 처리
2. 업데이트
3. 예외처리
이게 너무나도 중요하고 여기서 실수, 빵꾸가 다 발생한다.
큰 함수틀에서 어떻게 활용 될 수있나 잘 고려하고 작성하자.
하나 기분좋았던건, come배열과 어떤 배열만있으면 새롭게 넣어주는 함수를 만들어서
이리저리에 써먹었던것.
|
#1차원 배열을 넣으면 순서대로 come 배열의 순서대로 배열값을 다 넣어준다. ()
def come_maps_make(arr,come):
arr = deque(arr)
global maps
maps= [ [0]*n for _ in range(n)]
tx,ty = n//2,(n//2)
while not ( tx==0 and ty == 0) :
cx,cy = come[tx][ty]
if len(arr) == 0 : break
maps[cx][cy] = arr.popleft()
tx,ty=cx,cy
return
|
|
import sys
from collections import deque
sys.stdin = open("input_mirotower.txt",'r')
deb =0
n,m =map(int,input().split())
maps = [ list(map(int,input().split())) for _ in range(n)]
#우하좌상
dxs=[0,1,0,-1]
dys=[1,0,-1,0]
# 총라운드 수
def in_range(x,y) :
return 0<=x<n and 0<= y < n
def player_attack(d,p):
ox,oy = n//2,n//2
power = 0
for i in range(p) :
nx,ny = ox+dxs[d],oy+dys[d]
if in_range(nx,ny) :
power += maps[nx][ny]
maps[nx][ny] = 0
ox,oy = nx,ny
return power
def remake_line():
global maps
# maps 에다가 갱신해라 .
x,y = 0,0
num = 0
visited = [[False]*n for _ in range(n)]
line = deque()
visited[0][0] = True
possible = 1
come = [[0]*n for _ in range(n)]
while possible:
nx,ny = x+dxs[num],y+dys[num]
if nx == n//2 and ny == n//2 :
come[nx][ny] = (x,y)
break
if in_range(nx,ny) and not visited[nx][ny] :
if maps[nx][ny] != 0 :
line.append(maps[nx][ny])
come[nx][ny] = (x,y)
x,y=nx,ny
visited[nx][ny] = True
else :
num = (num+1)%4
#print(line)
#print(come)
line.reverse()
return_line = line.copy()
return_come = come.copy()
#이 아래부분을 함수화했으면 좋았을텐데
come_maps_make(line,come)
return (return_line,return_come)
#1차원 배열을 넣으면 순서대로 come 배열의 순서대로 배열값을 다 넣어준다. ()
def come_maps_make(arr,come):
arr = deque(arr)
global maps
maps= [ [0]*n for _ in range(n)]
tx,ty = n//2,(n//2)
while not ( tx==0 and ty == 0) :
cx,cy = come[tx][ty]
if len(arr) == 0 : break
maps[cx][cy] = arr.popleft()
tx,ty=cx,cy
return
def hey_4_monster(arr,come) :
#come 경로대로 arr index가 따라가는데, come 의 (x,y)값을 배열에 담아 뱉어줘야 어디를 지울수있는지 알수있다.
you_die = []
master = []
cnt = 0
x,y = n//2,n//2
for i in range(0,len(arr)-1) : # 인덱스 0번이 n//2,n//2-1 위치다.
tx,ty = come[x][y]
if arr[i] == arr[i+1]:
cnt +=1
you_die.append((tx,ty))
if i+1 == len(arr)-1 and cnt >= 3:
you_die.append(come[tx][ty])
master.append(you_die)
else :
if cnt >= 3 :
you_die.append((tx,ty))
master.append(you_die)
you_die = []
cnt = 0
x,y = tx,ty
if deb:
print(master)
if len(master) > 0 :
return (True,master)
return (False,[])
def destroy_4_monster(arr) :
# arr 는 지워야할 2차원 배열 튜플값
global maps
pp = 0
for ix in range(len(arr)) :
for (tx,ty) in arr[ix] :
#숫자값, idx
pp += maps[tx][ty]
maps[tx][ty] = 0
return pp
def monster_4_delete(arr,come_arr):
# arr 는 n//2,n//2-1 부터 쭈르륵 값을가지고있다.
if deb:
print(arr)
points = 0
possible = True
while possible :
check,check_arr = hey_4_monster(arr,come_arr)
if check :
points += destroy_4_monster(check_arr)
arr,_=remake_line()
#print(maps)
else :
return (points,arr)
return (points,[])
def line_extend(arr,come) :
#기존 배열
new_arr = []
cnt = 1
for i in range(len(arr)) : # 맨마지막일때 처리는?
if i+1 == len(arr) :
new_arr.append(cnt) # 개수
new_arr.append(arr[i]) # 숫자의크기
come_maps_make(new_arr,come)
return
if arr[i] == arr[i+1] :
cnt += 1
#cnt 증가시키고 계속 세기
else : # 다르다면,
new_arr.append(cnt) # 개수
new_arr.append(arr[i]) # 숫자의크기
cnt = 1
#짝궁 체크 마지막
if deb:
print(new_arr)
return 0
point=0
for _ in range(m) :
d,p = map(int,input().split())
point += player_attack(d,p)
(re_line,re_come) = remake_line()
px,after_4_delete_arr= monster_4_delete(re_line,re_come)
point += px
line_extend(after_4_delete_arr,re_come)
print(point)
|
'코딩 테스트' 카테고리의 다른 글
| [2021 삼성 코딩테스트 상반기 오전 2번] 코드트리 - 색깔 폭탄 파이썬 (1) | 2023.10.15 |
|---|---|
| [2023 삼성 코딩테스트 상반기 오전 1번] 코드트리 - 포탑부수기 파이썬 리뷰 2회차 대각선 탐색 (0) | 2023.10.12 |
| 파이썬에서 에러가 발생했을때 찾는법, 어디까지 들어가나 break 거는법 (0) | 2023.10.12 |
| [코드트리챌린지] 2022 삼성 코딩테스트 하반기 오후 2번 코드트리 - 산타의 선물 공장 2 파이썬 리뷰 (1) | 2023.10.11 |
| [코드트리챌린지] 재귀함수에 대한 고찰 - 파이썬 리뷰 (1) | 2023.10.10 |