2019 카카오 코딩 테스트 무지의 먹방 라이브, 길 찾기 게임
2019 카카오 코딩 테스트 4번 무지의 먹방 라이브, 5번 실패율 문제 풀이를 회고하는 포스팅입니다.
4. 무지의 먹방 라이브
문제 설명
자세한 문제 설명은 아래 페이지에서 참고해주세요
문제를 요약하면 무지가 먹방을 진행하는데 회전판에 올려져 있는 음식을 순서대로 1초씩 계속해서 섭취해 나간다. 방송이 시작한 후 K 초 후에 네트워크 장애로 방송이 중단되었다 다시 시작되는데, 다시 방송을 이어가기 위해서 몇 번 음식부터 다시 섭취해야 하는지 알아내는 문제이다.
음식을 먹는데 필요한 시간이 음식의 번호 순서대로 담겨 있는 배열과 K가 입력으로 주어진다.
K초가 지난후에 방송이 재개됐을 때 모든 음식을 다 섭취했다면 -1을 반환 하면된다.
정확성, 효율성 테스트가 같이 있는 문제이다.
문제 풀이
처음에 든 생각은 하나 하나 다 세어가면서 K초 뒤 먹어야 하는 음식의 번호가 무엇인지 알아내는 방법으로 푸는 방법은 당연히 아닐 것이란 생각이 들었다. 그렇다면 어떻게 빠르게 소거하지? 라는 생각을 하다가 회전판에 집중했다.
만약 1초만에 다 먹는 음식이 있다면 무지가 K초가 되기전 한 바퀴를 회전했을때 그 음식은 음식리스트에서 제거되어야한다. 두 바퀴를 회전했을 때는 당연히 리스트에 들어있는 모든 2가 제거되어야 한다. 이러한 점을 생각해봤을 때, 음식 리스트들이 오름차순으로 있으면 좋을 것 같았다. 또한, 한 사이클의 길이를 알고 있어야 할 것으로 생각했다.
이 아이디어로 문제를 풀어본 풀이는 다음과 같다.
음식 리스트에서 마지막 출력을 위한 음식의 인덱스를 알아야 하기 때문에 음식 리스트에 인덱스 값들을 추가한다.
반복문을 통해서 K가 한 사이클의 길이보다 크다면 계속해서 반복해주는데, 이 때 사이클의 수에 따른 음식의 수를 제거해준다. 만약 음식 리스트가 남은게 없다면 -1을 리턴해서 종료한다.
다 먹은 음식이 소거되고 남은 음식 리스트에서 한 사이클이 못되고 남아버린 K번째 음식을 리턴한다.
정답을 제출했더니 역시나 정확성은 다 맞았으나 효율성에서 다 틀렸다… 정렬을 이용해야하는데 잘 생각이 안났다..
효율성을 고려하려면 어떤 방법을 선택해야하지? 생각하다가 힙을 이용해서 위에서의 방법에서 정렬과 회전하는 방법을 조금 달리하였다.
음식 리스트에서 오름차순으로 정렬하고 마지막 출력을 위한 음식의 인덱스를 알아야 하기 때문에 음식 리스트에 인덱스 값들을 추가하고 힙으로 만든다. (정렬)
반복문을 통해서 K가 한 사이클이 아닌 한 번에 제거가 가능한 사이클의 횟수 만큼 K를 줄여나간다. 즉 (섭취할 시간이 남은 음식의 최소 시간 - 지나간 시간) * 사이클의 길이 만큼을 K에서 빼주는데, K가 이 값보다 작으면 그만 둔다.
첫 번쨰 방법은 리스트 형태로 계속해서 사이클마다 0인것을 체킹하여 새로운 리스트를 만들어서 저장했지만 이 방법에서는 힙 (우선순위 큐)의 특성을 이용해서 낮은 수부터 빼는 시간복잡도를 줄여 사이클을 반복해준다.
여기서 한 번 더 주의 해야한다. 첫 번째 풀이에서는 남은 K가 한 사이클만 남았기 때문에 그냥 K번째 음식의 인덱스를 뽑아내면 됐지만, 두 번째 방법에서 남은 K는 최대한 사이클을 돌아도 남은 음식들 중에서 가장 작은 시간의 음식을 제거하지 못하는 K이다.
즉, 앞으로 N바퀴를 돌아도 K가 남아있지만 남은 음식 중 최소 시간의 음식을 다 먹지 못하는 경우인 것이다. 따라서 한 사이클이 아니라 여러 사이클이 가능하고 모듈러 연산을 통해서 남은 바퀴 수를 다 돌은 것 처럼 계산하여 (K % 남은 음식의 수)번째 인덱스 값을 리턴한다.
코드 구현
첫 번째: 정확성만 맞은 코드
def solution(food_times, k) :
foods = []
for i in range(len(food_times)) :
foods.append([food_times[i], i + 1])
while True :
food_count = len(foods)
if food_count == 0 :
return -1
if (k < food_count) :
break
k -= food_count
temp = []
for index in range(len(foods)) :
foods[index][0] -= 1
if foods[index][0] != 0:
temp.append([foods[index][0], foods[index][1]])
foods = temp
return (foods[k][1])
두 번쨰: 정확성, 효율성 모두 맞은 코드 (힙을 이용한 코드)
import heapq
# heap을 이용하여 정확성, 효율성 모두 맞은 풀이
def solution_2(food_times, k) :
foods = []
for i in range(len(food_times)) :
foods.append([food_times[i], i + 1])
heapq.heapify(foods)
cycle_time = len(foods)
time_sum = 0
while ((foods[0][0] - time_sum) * cycle_time) <= k :
k -= ((foods[0][0] - time_sum) * cycle_time)
time_sum = foods[0][0]
cycle_time -= 1
heapq.heappop(foods)
if not foods:
return (-1)
foods = sorted(foods, key= lambda x:x[1])
return (foods[k % len(foods)][1])
5. 길 찾기 게임
문제 설명
자세한 문제 설명은 아래 페이지에서 참고해주세요
2차원 상의 점으로 노드들이 주어지는데, 이 노드들은 그래프 상으로 트리를 구성하고 있다. 이 트리를 이용해서 전위 순회값과 후위 순회값을 제출하는 문제이다.
문제 풀이
처음 문제를 보자마자 아 트리랑 prefix, postfix 만드는 문제네~ 하고 바로 진행을 시작했다.
쉬울 것만 같았는데 난관에 봉착했다. Node 클래스를 구현하고 Index를 기준으로 전위 순회와 후위 순회를 해야하기 때문에 Index값을 추가해주고 Y 값이 큰 값이 레벨이 낮은 노드이므로 Y값을 기준으로 내림차순 정렬을 하여 루트에서부터 X값을 비교하면 쉽게 풀리는 문제였다…
하지만 필자의 문제 풀이는 산으로 가기 시작했다. 괜히 이차원 배열을 이용한 특징이 있지 않을 까 하면서 트리를 만들어 나가기 시작했다. 그 삽질의 아이디어는 다음과 같다.
일단 Index를 추가하고 Y값을 기준으로 1차 정렬, X값을 기준으로 2차 정렬을 해준다. (X값은 그래프 상 왼쪽에서부터 바로바로 트리를 만들려는 의도이다.)
이 정렬된 리스트들을 트리를 만들기 이전에 트리의 Level 단위, 즉 Y값 단위로 쪼개준다. (부모 노드와 자식 노드의 관계로 나누기 위함이다.)
2가지의 경우의 수로 나눈다. 첫 번째는 노드의 정보 값이 오직 하나일 때이다. 이렇게 되면 트리의 레벨의 길이가 1이다. 이때는 [[1], [1]] 를 반환해준다. 이 경우가 아니라면 트리의 레벨의 길이가 2 이상이므로 고정적으로 루트 노드와 루트 노드의 자식노드를 연결해준다.
반복문 시작한다. 이 반복문은 트리의 레벨이 2인 경우(루트의 자식노드)를 부모 노드로 하는 것으로 시작하고 1씩 증가하여 (레벨 단위로 쪼갠 리스트의 수 - 2)번째가 부모 노드가 되는 것이 마지막이 된다. (i가 1씩 증가하는 인덱스라고 한다면 레벨 단위로 쪼갠 리스트의 i번째는 부모 노드 레벨이 되고 i + 1번째는 현재 비교될 노드들의 레벨이 된다.)
반복문에서는 경계값과 부모 노드의 X값, 현재 노드의 X값을 기준으로 부모 노드의 왼쪽에 들어갈지, 오른쪽에 들어갈지, 아니면 같은 레벨에서 다음 노드에게 넘겨 질지 결정한다.
- 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다.
- 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
위의 문제 조건을 이용한 방법으로 루트 노드로부터 경계값을 저장하면서 내려온다.
현재 노드의 X값이 부모 노드의 X값 보다 크고 부모 노드의 오른쪽 경계값보다 작다면 부모의 오른쪽 노드에 연결된다. 또한 현재 노드의 왼쪽 경계값이 부모 노드의 X값이 되고 (현재 노드의 조상들 중에서 왼쪽 방향으로 가장 가까운 노드이기 때문이다.) 오른쪽 경계값이 부모 노드의 경계값이 된다. (현재 노드의 왼쪽 경계값은 현재 노드가 오른쪽 자식이 되기 때문에 업데이트 되지만 오른쪽 경계값은 업데이트 될 필요없이 그대로 물려받는다.)
현재 노드의 X값이 부모 노드의 X값 보다 작고 부모 노드의 왼쪽 경계값보다 크다면 부모의 왼쪽 노드에 연결된다. 또한 현재 노드의 오른쪽 경계값이 부모 노드의 X값이 되고 (오른쪽 자식이 될때와 같은 이유로) 왼쪽 경계값은 부모 노드의 왼쪽 경계값을 물려받는다.
재귀 함수를 이용하여 preorder과 postorder을 구현하여 결과 값을 리턴한다. (파이썬의 경우 sys.setrecursionlimit(10**6)과 같은 코드로 재귀 허용범위를 늘려나야 런타임 에러가 안뜬다.)
이렇게 삽질의 결과로 96점이 나왔다.. 21번 테스트 케이스가 틀렸는데, 아직까지 어느부분이 문제가 되는지 모르겠다. (혹시 이 포스팅을 보시는 분들 중에서 문제를 찾는다면 댓글 부탁드립니다.) 다시 정신차리고 루트에서부터 위치를 찾아 연결해나가는 방법으로 100점을 얻어냈다.
코드 구현
공통 부분: node 클래스, preorder, postorder, 재귀 허용범위설정
import sys
sys.setrecursionlimit(10**6)
class node :
def __init__(self, x, y, idx) :
self.x = x
self.y = y
self.idx = idx
self.left = 0
self.right= 0
self.r_boundary = 0
self.l_boundary = 0
def get_attr(self) :
return (self.x, self.y, self.idx)
def get_left(self) :
return self.left
def get_right(self) :
return self.right
def set_right(self, right) :
self.right = right
def set_left(self, left) :
self.left = left
def get_l_boundary(self) :
return self.l_boundary
def get_r_boundary(self) :
return self.r_boundary
def set_r_boundary(self, value) :
self.r_boundary = value
def set_l_boundary(self, value) :
self.l_boundary = value
def preorder(root, result) :
if root == 0:
return
left = root.get_left()
right = root.get_right()
result.append(root.get_attr()[2])
preorder(left, result)
preorder(right, result)
return (result)
def postorder(root, result) :
if root == 0:
return
left = root.get_left()
right = root.get_right()
postorder(left, result)
postorder(right, result)
result.append(root.get_attr()[2])
return (result)
삽질한 코드: 96점
## 96점: 테스트 21번 실패
def solution_2(nodeinfo):
x_len = 0 # 최대 X 길이
# idx 추가
for idx, _node in enumerate(nodeinfo) :
if x_len < _node[0] :
x_len = _node[0]
_node.append(idx + 1)
# y값으로 1차정렬 x값으로 2차정렬
nodeinfo.sort(key= lambda x : (-x[1],x[0]))
top = nodeinfo[0][1]
level = [[]]
level_idx = 0
# level 단위로 나눈 리스트 생성
for x, y, idx in nodeinfo :
if top == y :
level[level_idx].append(node(x, y, idx))
else :
level.append([])
top = y
level_idx += 1
level[level_idx].append(node(x, y, idx))
# 레벨이 오직 1레벨: root만 존재: 고정적인 답 제출
if len(level) == 1 :
return [[1],[1]]
# 트리의 레벨이 2 이상이므로 root 노드를 셋팅해준다.
child = level[1]
parent = level[0][0]
px, py, pidx = parent.get_attr()
root = parent
root.set_l_boundary(0)
root.set_r_boundary(x_len + 1)
for c_node in child :
cx, cy, cidx = c_node.get_attr()
if cx > px :
c_node.set_l_boundary(px)
c_node.set_r_boundary(root.get_r_boundary())
root.set_right(c_node)
else :
c_node.set_l_boundary(root.get_l_boundary())
c_node.set_r_boundary(px)
root.set_left(c_node)
# 레벨 단위로 부모, 자식으로 하여 진행
for i in range(1, len(level) - 1) :
parent = level[i]
child = level[i + 1]
child_idx = 0
for p_node in parent:
for c_i in range(child_idx, len(child)) :
c_node = child[c_i]
r_b, l_b = p_node.get_r_boundary(), p_node.get_l_boundary()
px, py, pidx = p_node.get_attr()
cx, cy, cidx = c_node.get_attr()
# 부모의 오른쪽 자식
if px < cx and cx < r_b:
c_node.set_l_boundary(px)
c_node.set_r_boundary(r_b)
p_node.set_right(c_node)
# 부모의 왼쪽 자식
elif l_b < cx and cx < px:
c_node.set_l_boundary(l_b)
c_node.set_r_boundary(px)
p_node.set_left(c_node)
else :
# 이미 자식으로 등록된 노드들 등록 방지
child_idx = c_i
break
if c_i == len(child) : break
# preorder, postorder 진행
pre_result = []
post_result = []
preorder(root, pre_result)
postorder(root, post_result)
answer = []
answer.append(pre_result)
answer.append(post_result)
return answer
100점: 간단한 풀이
## 100점, 간단한 문제 풀이
def solution(nodeinfo):
for idx, _node in enumerate(nodeinfo) :
_node.append(idx + 1)
nodeinfo.sort(key= lambda x : (-x[1],x[0]))
root = 0
for x, y, idx in nodeinfo :
c_node = root
pre_node = 0
while True :
if root == 0 :
root = node(x, y, idx)
break
cx, cy, c_idx = c_node.get_attr()
if x < cx :
pre_node = c_node
c_node = c_node.get_left()
if c_node == 0 :
pre_node.set_left(node(x, y, idx))
break
else :
pre_node = c_node
c_node = c_node.get_right()
if c_node == 0 :
pre_node.set_right(node(x, y, idx))
break
return ([preorder(root, []), postorder(root, [])])
개인적 회고
간단하게 생각하면 4, 5번 모두 쉬운 문제였다. 하지만 필자는 너무 복잡하게 생각한 나머지 문제 푸는 시간이 오래걸렸고 효율적으로 코드를 구성하지 못하였다. 알고리즘을 공부하면서 좀 더 심플한 방법을 찾는 노력의 필요성을 느꼈다.
카카오의 효율성 문제는 보통 자료구조를 이용하는 방법을 요구하는 것 같다. 2020년도에서는 Trie, 2019년도에서는 Heap을 이용해서 효율성 문제를 맞출 수 있었다. 앞으로 카카오에서 효율성 문제에 부딪치게 된다면 어떤 자료구조를 사용해야할지 우선적으로 고려해보는 것이 좋을것 같다.