역대 카카오 인턴십 코딩테스트 문제 정리

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