[코드트리챌린지] 2022 삼성 코딩테스트 하반기 오후 2번 코드트리 - 산타의 선물 공장 2 파이썬 리뷰
드디어 dp 전처리문제를 풀었다 ㅋㅋㅋ -1일때 지나가지 않는 구간을 -1000으로 우주로 보내버린줄알았더니..
칸당 최대 수가 1000이라서 1000이 계속나오면 -1로 막힌 길을 뚫을수있는 형태가 되었다..
그래서 -10000000 으로 우주 끝까지 보내버리자 테스트케이스 통과 되어서 풀수있엇다.
그다음 문제는 hashmap 문제였는데 이거 할수있을꺼같은데 막상해보려고하니까 좀 버벅였다.
문제는 뭐엿냐면
6,6,4,9,6 인 배열이 주어지고 k=36일때 배열안에 서로다른 요소 2개를 골라서 두개를 곱한게 k인 개수를 내는건데
배열의 길이가 무려 10만까지도 늘어날수있는거라 무조껀 hashmap을 써야할것같았다.
나는 이걸 어떻게 할까 생각했냐면,
dict로 각 배열요소를 key값으로 몇개가 있는지 dict를 만든다.
d = { 6:3,4:1,9:1} 느낌. 그다음
set 은 중복자료구조라서 저걸먼저 6,4,9 로 만들고, 각기 다른 경우의 수를 잡는다 6,6랑 4,9개가 나온다.
그러면 6,6은 6을 1번이라도 가지고있으면 곱하기 d[6], 4,9도 마찬가지로 d[4]*d[9]를 곱한다.
그런 값들을 다 더하면 총 4가 나와서 이렇게 푸는게 맞지않을까 하고 막~ 코드로 쓰다가 시간 over되어버려서 GG쳐버렸다 ㅋㅋ
무튼 실력이 늘고있긴한거니까 좋은 반증이라 생각하고....
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
세상에 작년 오후 2번 손도 못대던 더블링크드 리스트를
자료구조 -> head, tail, next, prev 개념을 써서 직접 노가다로 풀어봤다.
물론 자료구조는 어케 돌아가나 컨닝좀했고, 대충 해놓고 하나하나 장독대 막는것처럼 디버깅하니까
시간이 진짜 너~무오래 걸리고 테스트케이스도 아주 최악이였다. 특히나
head,tail 처리, 아무것도 없을때, 딱 1개만있을때, 2개이상있을때 이렇게 나뉘어져 버려서 시간이 너무걸렸다...
내생각에 가장 크게 망해버린거는 ㅋㅋ
괜히 d={} 사용해서 벨트에 (head,tail) 로 자료구조로 관리해보려다가
여기서 그냥 개 꼬여버려가지고 ㅋㅋㅋ 시간이 너무 걸렸다 (괜히 자료구조 묶어보려는척! 해서 개망한 케이스 ㅋㅋ )
해설 답을보니 각 필요한 부분을 다 함수화를 해놨다.
예를들어
remove_head(b_num) -> 해당 벨트의 head제거.
그러면 머리만 뽕 빠지고 그다음 놈이 헤드가 되겠지.
만약에 크기가 1이라면 그냥 크기도 0만들고, head,tail정보도 다 -1이나 0 처럼 해버릴 수 있엇는데
또또또또 이걸 함수화 안해가지고 아주 일을 크게 만들었다.
다시 말하지만,
함수화 ->함수화-> 함수화 하는걸 되게 나는 두려워한다.
simulation 까지 만들어서 내부 운영을 함수화를 하는데
뭔가 내부운영 함수화를 그 함수에서 다만들지못하면 실수할것같은 그런느낌..
내생각엔 그냥 함수화했다가 헷갈려서 못찾으면 어떡하지 같은 강박이 있는것같다. 예전보단 좀 덜해졌지만..
계속보면,
push_head -> 해당 벨트에 머리넣기. 머리를 넣고 만약 그 벨트에 길이가 없다면 head tail 동시 갱신 이런거 처리.
하,,, 이거를 한번에 하려니까 아주 머리가 깨지는거였다 ㅋㅋ
그러면 front_change 같은경우도 저 머리 remove_head를 m_src랑 m_dst만 해주고 그냥 머리 넣어주면 아주 깔끔하게 코드를 짤수있는데 ..
하나 궁금한거. 해설코드에서 나누기는 어떻게 했나 확인해보니
나하고 비슷하게 했다. 벨트의 수량을 관리하는거에서 cnt//2 를 하고, 그걸 행렬에 넣은다음
하나하나 push head 해서 넣어버렸다..........
와..
이렇게 함수를 만들어서 여기저기에 써먹을수있으니..
??? : 흠. 이건 푸쉬헤드 만들어놓으면 여기저기쓸수있겟군요
를 알아채야한다는게 대단하다.
divide(elems) 역시나 코드가 깔끔.
나같은경우는 중간값 index를 읽다가 그 이전의 nxt 랑 그값의 prv 값을 잘라서 정말 나누어 버릴려고하는
head값 앞에다가 통째로 붙이고 head를 갱신하게 해버렷다.. 이거 디버깅하느라 정신나가는줄알았다.
벨트정보와 선물점수얻는건 링크드 리스트로 하면 정말 순식간에 알수있고..(이래서쓰는구나..근데 요즘추세가 우선순위큐가 나오니 과연 다시나올까 의문이다. 이거 생각하다가 사람들 얼마나 나가떨어졌으면.. )
그나마 해설코드에서도 구현을 좀한게
move_all (elems) 와같은 함수인데,
m_src와 m_dst의 벨트 위 숫자수 를 비교하고,
아닌경우는 헤드교체, nxt와 prv값들을 갱신해주고
m_src를 다 0으로 초기화.
확실히 자료구조만 듣고 내가 직접다 구현해보니까 해설코드를 봐도 무슨말인지 알 수 있게 됐다.
진짜 너무신기하네 ㅋㅋㅋ..
그다음 선물상자 갱신 .
아마 이번에는 우선순위큐문제가 나와서 10월15일에 시험보기전에 코드트리 체점기를 풀어보고 들어갈꺼같다.
그것마저 할줄안다면
나설마 2번 풀어버리는거 아닐까??????(응아니야)
코드올리고 갑니다.
|
import sys
from collections import deque
sys.stdin = open("input_santa2.txt",'r')
deb =0
belt_info = {} # 벨트들의 앞뒤 head,tail 을 가리키는 dict
#헤드가 인덱스 0 을 말하고
#테일이 가장 인덱스가 큰 맨뒤에있는거
nxt = [-1]*100000 #상자들의 next,prev를 결정
prv = [-1]*100000
#임시로 관리하는거라 실제 len(deque) 이렇게 관리하기 어렵다. 링크드리스트라 따로 벨트마다 개수를 세는 배열필요
belt_cnt = []
def make_fac(strings) :
global belt,belt_info
n=int(strings[1])
belt = {}
for num in range(n) :
belt[num] = deque()
m=int(strings[2])
#초기선물들의 next,prev,head,tail 관리해보자.
for j in range(m) :
belt[int(strings[3+j])-1].append((1+j)) # 선물의 인덱스번호
for i in range(n):
if len(belt[i]) == 0 :
belt_cnt.append(len(belt[i]))
belt_info[i] = ((-1,-1))
continue
belt_info[i] = ((belt[i][0],belt[i][-1]))
belt_cnt.append(len(belt[i]))
for x in range(0,len(belt[i])-1 ):
nxt[belt[i][x]] =(belt[i][x+1])
prv[belt[i][x+1]]= belt[i][x]
if deb:
print(belt)
print(belt_cnt)
print(nxt)
print(prv)
print(belt_info)
return
def move_all(m_src,m_dst):
global belt
m_src=int(m_src)
m_dst=int(m_dst)
m_src -=1
m_dst -=1
if belt_cnt[m_src] == 0 :
print(belt_cnt[m_dst])
return
if belt_cnt[m_dst] == 0 : # dst에 물건이없으면 그대로 옮긴다.
belt_info[m_dst] = belt_info[m_src]
belt_info[m_src] = (-1,-1)
belt_cnt[m_dst] = belt_cnt[m_src]
belt_cnt[m_src] = 0
else : # head
#head,tail
dst_head,dst_tail = belt_info[m_dst]
src_head,src_tail = belt_info[m_src]
belt_info[m_dst] = (src_head,dst_tail)
belt_info[m_src] = (-1,-1)
nxt[src_tail] = dst_head
prv[dst_head] = src_tail
belt_cnt[m_dst] += belt_cnt[m_src]
belt_cnt[m_src] = 0
print(belt_cnt[m_dst])
if deb:
print(belt)
print(belt_cnt)
print(nxt)
print(prv)
print(belt_info)
return
def front_change(m_src,m_dst) :
global belt
m_src=int(m_src)
m_dst=int(m_dst)
m_dst-=1
m_src-=1
if belt_cnt[m_src] == 0 and belt_cnt[m_dst] == 0: #아무것도 없는경우
pass
elif belt_cnt[m_dst] == 0 : # src만 옮긴다
src_head,src_tail = belt_info[m_src]
if belt_cnt[m_src] == 1 :
src_tail = -1
belt_info[m_src] = (nxt[src_head],src_tail)
prv[nxt[src_head]] = -1
nxt[src_head] = -1
prv[src_head] = -1
belt_cnt[m_dst] = 1
belt_cnt[m_src] -= 1
belt_info[m_dst] = (src_head,src_head)
elif belt_cnt[m_src]== 0 : # dst 만 옮긴다.
dst_head,dst_tail = belt_info[m_dst]
if dst_head == dst_tail :
belt_info[m_dst] = (-1,-1)
else :
belt_info[m_dst] = (nxt[dst_head],dst_tail)
prv[nxt[dst_head]] = -1
nxt[dst_head] = -1
prv[dst_head] = -1
belt_cnt[m_src] = 1
belt_cnt[m_dst] -= 1
belt_info[m_src] = (dst_head,dst_head)
else : # 둘다 앞에놈만 옮긴다
#만약에 옮겨지는애들이 크기가 1인경우 head,tail 이 같아야한다. 유의
src_head,src_tail = belt_info[m_src]
dst_head,dst_tail = belt_info[m_dst]
src_nxt_head = nxt[src_head]
dst_nxt_head = nxt[dst_head]
prv[src_nxt_head]=dst_head
prv[dst_nxt_head]=src_head
nxt[src_head]=nxt[dst_head]
nxt[dst_head]=src_nxt_head
if belt_cnt[m_dst] == 1 :
dst_tail = src_head
if belt_cnt[m_src] ==1 :
src_tail = dst_head
belt_info[m_dst] = src_head,dst_tail
belt_info[m_src] = dst_head,src_tail
#3prv가 이상하다 !
print(belt_cnt[m_dst])
if deb:
print(belt)
print(belt_cnt)
print(nxt)
print(prv)
print(belt_info)
return
def divide(m_src,m_dst) :
global belt
m_src=int(m_src)
m_dst=int(m_dst)
m_dst-=1
m_src-=1
length = belt_cnt[m_src]
if length <= 1 :
print(belt_cnt[m_dst])
return
half = (length // 2 )
src_head,src_tail = belt_info[m_src]
dst_head,dst_tail = belt_info[m_dst]
item = src_head
for i in range(1,belt_cnt[m_src]): #인덱스 i 나타낸다.
item = nxt[item]
if i == half :
#여기서 검출된 item이 src의 헤드가 되어야한다.
belt_info[m_src] = item,src_tail
nxt[prv[item]] = dst_head
goodbye = prv[item] #goodbye는 dst의 헤드를 nxt로
prv[dst_head] = goodbye
if dst_tail == -1 :
dst_tail = prv[item]
prv[item] = -1
belt_info[m_dst] = (src_head,dst_tail)
belt_cnt[m_dst] += i
belt_cnt[m_src] -= i
break
print(belt_cnt[m_dst])
if deb:
print(belt_cnt)
print(nxt)
print(prv)
print(belt_info)
return
def inform_present(p_num):
#해당 선물의 앞선물의 번호 a와 뒤선물의 번호 b 일때 a+2*b
#없는경우는 -1,-1 을 넣는다.
p_num = int(p_num)
a=prv[p_num]
b=nxt[p_num]
point = a+2*b
print(point)
return
def infrom_belt(b_num) :
global belt
b_num = int(b_num)
b_num -=1
(a,b),c=belt_info[b_num],belt_cnt[b_num]
point = a+2*b+3*c
print(point)
return
q = int(input())
for _ in range(q):
strings = list(input().split())
if strings[0] == '100' :
make_fac(strings)
elif strings[0] == '200':
move_all(strings[1],strings[2])
elif strings[0] == '300':
front_change(strings[1],strings[2])
elif strings[0] == '400':
divide(strings[1],strings[2])
elif strings[0] == '500':
inform_present(strings[1])
elif strings[0] == '600':
infrom_belt(strings[1])
|