2023 KAKAO BLIND RECRUITMENT 문제풀이 (Python)

개인정보 수집 유효기간

단순 구현 문제이고 "년.월.일" 형태를 "일"로 바꿔 계산합니다. 문제를 풀면서 날짜 계산에 주의해야 합니다.

	def solution(today, terms, privacies):
	answer = []
	terms = {term[0]:int(term[2:]) for term in terms}
	today=list(map(int,today.split('.')))
	f=lambda y,m,d : y*12*28+m*28+d
	for i,p in enumerate(privacies):
	a,b=p.split()
	c=list(map(int,a.split('.')))
	if f(*today)>f(*c)+terms[b]*28-1: answer.append(i+1)
	return answer

view raw 2023kakao_1.py hosted with ❤ by GitHub

택배 배달과 수거하기

문제가 지금도 잘 이해가 되지 않지만 "각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다." 라는조건을 통해 물건을 나눠 배달하거나 수거할 수 있다고 생각하여 다음과 같이 구현했습니다.

	def solution(cap, n, deliveries, pickups):
	answer = 0
	a,b,s1,s2,t1,t2=0,0,[],[],[],[]
	for i,(x,y) in enumerate(zip(reversed(deliveries),reversed(pickups))):
	a+=x; b+=y
	if x: t1.append(n-i)
	if y: t2.append(n-i)
	while a>=cap:
	s1.append(t1[0]); t1=[] if a==cap else [n-i]; a-=cap
	while b>=cap:
	s2.append(t2[0]); t2=[] if b==cap else [n-i]; b-=cap
	if len(t1): s1.append(t1[0])
	if len(t2): s2.append(t2[0])
	for i in range(max(len(s1),len(s2))):
	if i<len(s1) and i<len(s2): answer+=max(s1[i],s2[i])*2
	elif i<len(s1): answer+=s1[i]*2
	elif i<len(s2): answer+=s2[i]*2
	return answer

view raw 2023kakao_2.py hosted with ❤ by GitHub

이모티콘 할인행사

각각의 케이스마다 완전탐색하여 구현할 수 있습니다.

	def solution(users, emoticons):
	answer = [0,0]
	d,s=[],[[]]
	while len(s):
	x=s[-1]; s.pop()
	if len(x)==len(emoticons):
	d.append(x)
	else:
	for i in [10,20,30,40]:
	s.append(x+[i])
	for d_ in d:
	eplus,money = 0,0
	for u1, u2 in users:
	tot=sum([a*(1-b*0.01) for a,b in zip(emoticons,d_) if b>=u1])
	if tot>=u2: eplus+=1
	else: money+=tot
	if answer[0]<eplus or (answer[0]==eplus and answer[1]<money):
	answer=[eplus,money]
	return answer

view raw 2023kakao_3.py hosted with ❤ by GitHub

표현 가능한 이진트리

어떠한 트리가 존재하고 완전이진트리가 될 수 있는 길이만큼 0으로 패딩했을 때 완전이진트리를 형성할 수 있는지 물어보는 문제입니다.

이 문제의 중요한 조건은 부모 노드가 0일때, 자식 노드가 1이 되어서는 안 됩니다. 반면에, 부모 노드가 0인 경우 자식 노드가 0인 경우는 가능하므로 주의해야 합니다.

istree라는 함수를 추가하여 조건에 맞는 완전이진트리를 형성할 수 있는지 체크합니다. queue에 (start,end,parent)로 넣어 서브트리마다 조건을 충족하는지 확인합니다.

완전이진트리를 만들고 가운데 값이 루트가 되며 1이어야 합니다.

 

1. 7(111)
111는 이미 완전이진트리입니다. 

2. 42(101010)
맨 앞에 0을 하나만 추가하여 0101010을 만들면 다음과 같이 완전이진트리가 됩니다.
1 ┬ 1 ┬ 0
    |     └ 0
   └ 1 ┬ 0
          └ 0


3. 5(101)
완전이진트리가 되도록 0을 두개 추가하여 000101을 만들었지만 조건에 따라 불가능합니다.
1 ┬ 0 ┬ 0
    |     └ 0
   └ 0 ┬ 0
           └ 1

4. 63(111111)
완전이진트리가 되도록 0을 하나 추가하여 0111111을 만들면 다음과 같이 완전이진트리가 됩니다.
1 ┬ 1 ┬ 0
    |     └ 1
   └ 1 ┬ 1
          └  1

5. 111(1101111)
1101111은 이미 완전이진트리입니다.
1 ┬ 1 ┬ 1
    |     └ 0

   └ 1 ┬ 1
          └ 1

6. 95(1011111)
1011111은 완전이진트리의 길이를 가지고 있지만 조건에 따라 불가능합니다.
1 ┬ 0 ┬ 1
    |     └ 1
   └ 1 ┬ 1
          └ 1

	def solution(numbers):
	from bisect import bisect_left
	answer = []
	def istree(b):
	x=len(b)//2
	if b[x]!='1':
	return 0
	q=[(0,x-1,1),(x+1,len(b)-1,1)] # (s,e,parent)
	while q:
	s,e,p=q[-1]; q.pop()
	if s<=e:
	t=(s+e)//2
	if p=='0' and b[t]=='1':
	return 0
	if s<e:
	q.append((s,t-1,b[t])); q.append((t+1,e,b[t]))
	return 1
	l = [(1<<i)-1 for i in range(0,16)]
	for n in numbers:
	s = bin(n)[2:]
	ids = bisect_left(l,len(s))
	if len(s)!=l[ids]:
	s='0'*(l[ids]-len(s))+s
	answer.append(istree(s))
	return answer

view raw 2023kakao_4.py hosted with ❤ by GitHub

표 병합

Union-Find와 같은 아이디어로 문제를 해결했습니다.

Table은 각각의 좌표마다 가리키는 좌표를 저장합니다. 병합하지 않았다면 자기 자신을 가리킬 것이고 병합되었다면 병합에 참여한 배열 중 입력되는 첫 번째 좌표를 가리키도록 구현했습니다. Value는 각각의 좌표마다 저장된 실제 값입니다.

	def solution(commands):
	answer = []
	table=[[(i,j) for j in range(51)] for i in range(51)]
	value=[['-' for j in range(51)] for i in range(51)]
	for cmd in commands:
	cmd=cmd.split()
	if cmd[0]=='UPDATE':
	if len(cmd[1:])==3:
	r,c,v=cmd[1:]
	r,c=table[int(r)][int(c)]
	value[r][c]=v
	else:
	v1,v2=cmd[1:];
	for i in range(1,51):
	for j in range(1,51):
	if value[i][j]==v1: value[i][j]=v2
	if cmd[0]=='MERGE':
	r1,c1,r2,c2=list(map(int,cmd[1:]))
	if r1==r2 and c1==c2: continue
	r1,c1=table[r1][c1]
	r2,c2=table[r2][c2]
	if value[r1][c1]=='-' and value[r2][c2]!='-':
	value[r1][c1]=value[r2][c2]
	for i in range(51):
	for j in range(51):
	if table[i][j]==(r2,c2):
	table[i][j]=(r1,c1)
	if cmd[0]=='UNMERGE':
	r,c=cmd[1:]
	r1,c1=table[int(r)][int(c)]
	v=value[r1][c1]
	for i in range(51):
	for j in range(51):
	if table[i][j]==(r1,c1):
	table[i][j]=(i,j)
	value[i][j]='-'
	value[int(r)][int(c)]=v
	if cmd[0]=='PRINT':
	r,c=list(map(int,cmd[1:]))
	a,b=table[r][c]
	if value[a][b]!='-': answer.append(value[a][b])
	else: answer.append('EMPTY')
	return answer

view raw 2023kakao_5.py hosted with ❤ by GitHub

미로 탈출 명령어

현재 위치에서 도착지까지 거리와 현재 이동한 거리를 합한 값이 k를 넘기는지 확인하면서 탐색하는 것이 중요합니다. 탐색 방향은 ['d', 'l', 'r', 'u']으로 이동하고 가장 먼저 도착지에 도착하는 문자열이 답이 됩니다.

	def solution(n, m, x, y, r, c, k):
	from collections import deque
	answer = 'z'*k
	dx, dy, dz = [1,0,0,-1], [0,-1,1,0], ['d','l','r','u']
	q = deque()
	q.append([x,y,0,''])
	def manhattan(a,b):
	return abs(a[0]-b[0])+abs(a[1]-b[1])
	if manhattan((x,y),(r,c))>k or (k-manhattan((x,y),(r,c)))%2==1:
	return 'impossible'
	while q:
	x_, y_, d, s = q.popleft()
	if x_ == r and y_ == c and d == k:
	answer=min(answer,s)
	break
	if manhattan((x_,y_),(r,c))+d>k:
	continue
	for i in range(4):
	nx, ny = x_+dx[i], y_+dy[i]
	if 0<nx<=n and 0<ny<=m:
	if manhattan((nx,ny),(r,c))+d+1>k: continue
	q.append([nx,ny,d+1,s+dz[i]])
	break
	return answer if answer!='z'*k else 'impossible'

view raw 2023kakao_6.py hosted with ❤ by GitHub

1,2,3 떨어트리기

...