2019 카카오 개발자 겨울 인턴십
| 알고리즘 |
빈도 |
문제 |
| 시뮬레이션 |
1 |
크레인 인형뽑기 게임(Level 1) |
| 문자열 |
1 |
튜플(Level 2) |
| 완전 탐색 |
1 |
불량 사용자(Level 3) |
| DFS/BFS |
0 |
|
| 이진 탐색 |
1 |
징검다리 건너기(Level 3) |
| 그래프 |
1 |
호텔 방 배정(Level 4) |
| 재귀 |
1 |
호텔 방 배정(Level 4) |
| 투 포인터 |
0 |
|
1. 크레인 인형뽑기 게임
# 시뮬레이션 (구현) : 2차원 스택(리스트) 구성
def solution(board, moves):
answer = 0
basket=list()
# board -> list(list()) 구성 (원하는 형태의 2차원 스택으로 변경)
b=[list() for _ in range(len(board[0]))]
for i in range(len(board[0])):
for deep in range(len(board)-1,-1,-1):
if board[deep][i]==0:
break
else:
b[i].append(board[deep][i])
# len(moves)만큼 인형 꺼내기 (만약 empty라면 꺼내지 않음)
for m in moves:
# 파이썬스러운 empty 체크 (https://codechacha.com/ko/python-check-empty-list/)
if b[m-1]:
doll = b[m-1].pop()
# 꺼낸 것과 basket의 제일 위에 것 비교
# 같으면 basket pop하고 +2
if basket and basket[-1]==doll:
basket.pop()
answer+=2
# 다르면 basket append
else:
basket.append(doll)
return answer
2. 튜플
from collections import defaultdict
def solution(s):
# defaultdict
d = defaultdict(int)
# 문자열 처리
l=[int(a) for a in s.replace('{', '').replace('}','').split(',')]
for n in l:
d[n]+=1
# dictionary value 기준 내림차순 정렬
return [item[0] for item in sorted(d.items(), key = lambda item: item[1], reverse=True)]
3. 불량 사용자
# 완전 탐색
from itertools import product
def solution(user_id, banned_id):
ll=list()
for b in banned_id:
cand=set(u for u in user_id if len(u)==len(b))
for i in range(len(b)):
# *이면 freepass
if b[i]=='*':
continue
else:
for s in list(cand):
if s[i]!=b[i]:
cand.remove(s)
ll.append(cand)
# 단일 튜플 내 동일한 원소 제거 및 순서만 다른 중복 튜플 제거
p1=set(tuple(set(p)) for p in product(*ll) if len(set(p))==len(p))
answer = len(p1)
return answer
4. 징검다리 건너기
# n은 징검다리를 건너는 최대 친구 수
def isValid(stones, k, n):
cumul=0
for stone in stones:
if stone-n<=0:
cumul+=1
if cumul==k:
return False
else:
cumul=0
return True
def solution(stones, k):
start, end = 1, 200000001
# 이진 탐색의 기본 틀 안에서 동작해야 함
# 1. start <= end
# 2. start = mid+1
# 3. end = mid -1
while start<=end:
mid = (start+end)//2
if isValid(stones, k, mid):
start=mid+1
else:
end=mid-1
answer = start
return answer
5. 호텔 방 배정
import sys
sys.setrecursionlimit(10000)
from collections import defaultdict
def solution(k, room_number):
answer = []
d=defaultdict(int)
for r in room_number:
answer.append(find_empty_room(r,d))
return answer
def find_empty_room(r, d):
if d[r]==0:
d[r]=r+1
return r
else:
nr=find_empty_room(d[r],d)
d[r]=nr+1
return nr
2020 카카오 인턴십
| 알고리즘 |
빈도 |
문제 |
| 시뮬레이션 |
1 |
키패드 누르기(Level 1) |
| 문자열 |
1 |
수식 최대화(Level 2) |
| 완전 탐색 |
1 |
수식 최대화(Level 2) |
| DFS/BFS |
1 |
경주로 건설(Level 3), 동굴 탐험(Level 4) |
| 이진 탐색 |
0 |
|
| 그래프 |
0 |
|
| 재귀 |
0 |
|
| 투 포인터 |
1 |
보석 쇼핑(Level 3) |
1. 키패드 누르기
def calculate_distance(t1, t2):
return abs(t1[0]-t2[0])+abs(t1[1]-t2[1])
def select_hand(l,r,m,hand):
keypad={1:(0,0),2:(0,1),3:(0,2),4:(1,0),5:(1,1),6:(1,2),7:(2,0),8:(2,1),9:(2,2),'*':(3,0),0:(3,1),'#':(3,2)}
c1,c2=calculate_distance(keypad[l],keypad[m]),calculate_distance(keypad[m],keypad[r])
if c1>c2:
return 'R'
elif c1<c2:
return 'L'
else:
return 'L' if hand=='left' else 'R'
def solution(numbers, hand):
answer = ''
l,r='*','#'
for n in numbers:
if n in (2,5,8,0):
h=select_hand(l,r,n,hand)
print(h)
if h=='L':
l=n
answer+='L'
else:
r=n
answer+='R'
elif n in (1,4,7):
l=n
answer+='L'
else:
r=n
answer+='R'
return answer
2. 수식 최대화
from itertools import permutations
from copy import deepcopy
def solution(expression):
candi=[]
parsed=[]
# 연산자 기준 파싱
s=e=0
while e<=len(expression):
if e==len(expression):
parsed.append(expression[s:e])
break
elif expression[e] in ('+','-','*'):
parsed.append(expression[s:e])
parsed.append(expression[e])
s=e+1
e=s+1
else:
e+=1
for case in list(permutations(['+','-','*'],3)):
tp=deepcopy(parsed)
for exp in case:
i=0
while i<len(tp):
if tp[i]==exp:
tp[i-1]=eval(str(tp[i-1])+exp+str(tp[i+1]))
del tp[i]
del tp[i]
else:
i+=1
candi.append(abs(tp[0]))
answer = max(candi)
return answer
3. 보석 쇼핑
# 투-포인터
# set
# dict
from collections import defaultdict
def solution(gems):
answer=[]
length=len(gems)
tobuy=set(gems)
shop=defaultdict(int)
s=e=0
shop[gems[0]]+=1
tobuy.remove(gems[0])
while s<=e and e<len(gems):
if len(tobuy)==0:
if e-s<length:
answer=[s+1,e+1]
length=e-s
shop[gems[s]]-=1
if shop[gems[s]]==0:
tobuy.add(gems[s])
s+=1
else:
e+=1
if len(gems)==e:
break
if gems[e] in tobuy:
tobuy.remove(gems[e])
shop[gems[e]]+=1
return answer
4. 경주로 건설
# BFS 유형 : 경로 탐색
from collections import deque
# 3차원 costMap 메모이제이션으로 유망성 판단 후 BFS 백트래킹
def solution(board):
N=len(board)
costMap=[[[999999999 for _ in range(4)] for _ in range(N)] for _ in range(N)]
q=deque()
dr, dc = (-1,0,1,0), (0,1,0,-1)
# r, c, cost, past-direction
q.append((0,0,0,-1))
costMap[0][0][0]=costMap[0][0][1]=costMap[0][0][2]=costMap[0][0][3]=0
while q:
r, c, cost, pd = q.popleft()
for d in range(4):
nr,nc=r+dr[d],c+dc[d]
# 움직일 수 있는 보드인지 체크
if 0<=nr<N and 0<=nc<N and board[nr][nc]==0:
# cost 체크 and costMap 체크
plusCost=100 if d==pd or pd==-1 else 600
if cost+plusCost<costMap[nr][nc][d]:
costMap[nr][nc][d]=cost+plusCost
q.append((nr,nc,cost+plusCost,d))
answer = min(costMap[N-1][N-1])
return answer
5. 동굴 탐험
# dfs/bfs 유형 두번째(땅 따먹기)
from collections import defaultdict
def solution(n, path, order):
pd=defaultdict(set)
od=dict()
remind=defaultdict(list)
for p in path:
pd[p[0]].add(p[1])
pd[p[1]].add(p[0])
for o in order:
if o[1]==0:
return False
od[o[1]]=o[0]
visited=set()
visited.add(0)
stk=list()
stk.append(0)
while stk:
node=stk.pop()
visited.add(node)
if len(visited)==n:
return True
if remind[node]:
for r in remind[node]:
stk.append(r)
for p in pd[node]:
if p in visited:
continue
if p in od and od[p] not in visited:
remind[od[p]].append(p)
else:
stk.append(p)
return False
