2018년 카카오 blind 코딩 테스트 - 길 찾기 게임 python
문제 설명 : 길 찾기 게임 - 이진 트리(binary tree) 검색길 찾기 게임 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다.
라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다.
그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다.
라이언은 아래와 같은 특별한 규칙으로 트리 노드들을 구성한다.
트리를 구성하는 모든 노드의 x, y 좌표 값은 정수이다. 모든 노드는 서로 다른 x값을 가진다. 같은 레벨(level)에 있는 노드는 같은 y 좌표를 가진다. 자식 노드의 y 값은 항상 부모 노드보다 작다. 임의의 노드 V의 왼쪽 서브 트리(left subtree)에 있는 모든 노드의 x값은 V의 x값보다 작다. 임의의 노드 V의 오른쪽 서브 트리(right subtree)에 있는 모든 노드의 x값은 V의 x값보다 크다.
아래 예시를 확인해보자.
라이언의 규칙에 맞게 이진트리의 노드만 좌표 평면에 그리면 다음과 같다. (이진트리의 각 노드에는 1부터 N까지 순서대로 번호가 붙어있다.)
위 이진트리에서 전위 순회(preorder), 후위 순회(postorder)를 한 결과는 다음과 같고, 이것은 각 팀이 방문해야 할 순서를 의미한다.
전위 순회 : 7, 4, 6, 9, 1, 8, 5, 2, 3 후위 순회 : 9, 6, 5, 8, 1, 4, 3, 2, 7
다행히 두 팀 모두 머리를 모아 분석한 끝에 라이언의 의도를 간신히 알아차렸다.
그러나 여전히 문제는 남아있다. 노드의 수가 예시처럼 적다면 쉽게 해결할 수 있겠지만, 예상대로 라이언은 그렇게 할 생각이 전혀 없었다.
이제 당신이 나설 때가 되었다.
곤경에 빠진 카카오 프렌즈를 위해 이진트리를 구성하는 노드들의 좌표가 담긴 배열 nodeinfo가 매개변수로 주어질 때, 노드들로 구성된 이진트리를 전위 순회, 후위 순회한 결과를 2차원 배열에 순서대로 담아 return 하도록 solution 함수를 완성하자.
제한사항
|
출처 : https://programmers.co.kr/learn/courses/30/lessons/42892
문제 풀이
문제는 이진 트리를 구성하고, 전위 순회(preorder), 후위 순회(postorder)로 나온 값을 돌려주면 되는 문제입니다.
즉 이진 트리를 구성하기 위한 class를 구현하는 것이 필수죠.
또한 x축과 y축 정보를 잘 이용해야 합니다. y축 기준으로 비교 시에 값이 높을 수록 부모 노드에 해당합니다.
그리고 x축 기준으로 비교 시에 작다면 왼쪽 자식 노드가, 크다면 오른쪽 자식 노드가 되겠죠.
최종적으로 전위 순회, 후위 순회를 하고 인덱스를 반환해야하므로 필요한 데이터는 x,y,index 정보가 필요합니다.
이진 트리를 생성할 때는 y축 값 정렬을 하고 제일 높은 값을 가진 Node가 루트 노드가 됩니다.
그 루트 노드를 기준으로 다음의 레벨에 있는 노드 들을 자식 노드로 둘 것인데 이 때 x 값 기준으로 왼쪽, 오른쪽 자식 노드로 선택하면 되겠죠.
x축 기반으로 boundary를 계속 주면서 내려가야 부모 노드를 잘못 설정하는 경우가 없을 것입니다.
또한 효율성을 따지기 위해서는 recursion의 limit을 줘야 합니다. 제한 사항에서 모든 노드 좌표 값은 10만 이하이므로 그걸로 제한을 주면 됩니다.
import sys
sys.setrecursionlimit(10 ** 6)
|
[1] 이진 트리 Node를 Class로 구현합니다.
- Class로 구현할 때는 부모 노드의 x축(x)와 left_bound, right_bound를 봐야하고, 인덱스인 (id)가 필요합니다.
- x, id, left_bound, right_bound, left_node(왼쪽 자식 노드), right_node(오른쪽 자식 노드)
[2] 다음은 이쁘게 이진 트리 Node에 넣어줘야 합니다. 그러기 위해서 enumerate()를 써서 현재 데이터를 (x, y, index)로 바꿔줍니다. [[x, y, value], … ]
ex) [[5, 3, 1], [11, 5, 2], [13, 3, 3], [3, 5, 4], [6, 1, 5], [1, 3, 6], [8, 6, 7], [7, 2, 8], [2, 2, 9]]
[3] y축의 값을 높은 순으로 배치하기 위해서 내림차순 sorted(reverse=True) 정렬합니다.
ex) [[8, 6, 7], [11, 5, 2], [3, 5, 4], [5, 3, 1], [13, 3, 3], [1, 3, 6], [7, 2, 8], [2, 2, 9], [6, 1, 5]]
[4] 같은 레벨 단위로 묶어서 관리하는 level_array를 만듭니다.
ex) [[(8, 7)], [(11, 2), (3, 4)], [(5, 1), (13, 3), (1, 6)], [(7, 8), (2, 9)], [(6, 5)]]
[5] level_array를 x축으로 정렬해야 왼쪽, 오른쪽 정리하기 편합니다.
ex) [[(8, 7)], [(3, 4), (11, 2)], [(1, 6), (5, 1), (13, 3)], [(2, 9), (7, 8)], [(6, 5)]]
[6] 제일 높은 값을 root 노드로 합니다.
[7] 그 다음 레벨부터 for문 돌면서 살펴보면 되는데 이때 왼쪽 자식 노드와 오른쪽 자식 노드를 살펴봅니다.
- 부모의 x 좌표와 left_bound 사이에 있다면 왼쪽 자식 노드가 됩니다.
- 부모의 x 좌표와 right_bound 사이에 있다면 오른쪽 자식 노드가 됩니다.
[8] preorder 순회를 구현합니다. value->left_node->right_node로 재귀 함수로 구현합니다.
[9] postorder 순회를 구현합니다. left_node -> right_node -> value로 재귀 함수로 구현합니다.
[10] 순회한 결과를 반환합니다.
import sys
sys.setrecursionlimit(10 ** 6)
# 이진 트리 Node Class로 구현
class Node:
def __init__(self, x, id, left_bound, right_bound):
self.x = x # 자신의 x좌표로 자식 노드가 참조
self.id = id # 인덱스
self.left_bound = left_bound # 왼쪽 boundary - 왼쪽 자식노드 판별
self.right_bound = right_bound # 오른쪽 boundary - 오른쪽 자식 노드 판별
self.left_node = None # 왼쪽 자식노드
self.right_node = None # 오른쪽 자식 노드
preorder_result = []
postorder_result = []
# 전위 순회(Value -> L -> R) 재귀 함수로 구현
def preorder(node):
preorder_result.append(node.id)
if node.left_node is not None:
preorder(node.left_node)
if node.right_node is not None:
preorder(node.right_node)
# 후위 순회(L -> R -> Value) 재귀 함수로 구현
def postorder(node):
if node.left_node is not None:
postorder(node.left_node)
if node.right_node is not None:
postorder(node.right_node)
postorder_result.append(node.id)
def solution(nodeinfo):
answer = [[]]
# 이진트리로 구성하면되는 문제이다.
# x축(왼쪽/오른쪽 노드)과 y축(level)
# 효율성을 고려하자면 x축 범위를 제한둘 수 있다.
# 우선 (x, y, index)로 변경하자
nodeinfo = [value + [idx + 1] for idx, value in enumerate(nodeinfo)]
# y축 레벨 단위로 정렬하자. 높을 수록 부모 노드에 해당하므로, 내림 차순으로 정렬 reverse=True
nodeinfo = sorted(nodeinfo, key=lambda x: x[1], reverse=True)
level_array = [] # 같은 y에 있는 List에 여러 개의 x 좌표가 들어가도록 구성
now = -1
for item in nodeinfo:
y = item[1]
if y != now: # 현재와 같은 레벨인지 확인한다.
level_array.append([]) # 아니면 새로운 층으로 추가
now = y
level_array[len(level_array)-1].append((item[0], item[2])) # 추가된 층으로 x 값과 인덱스 삽입
# 같은 층에 있는 x 기준으로 오름 차순으로 정렬
for i in range(len(level_array)):
level_array[i] = sorted(level_array[i])
# root 노드를 넣는다.
root = Node(level_array[0][0][0], level_array[0][0][1], 0, 100000)
# 부모 노드를 관리하는 리스트
parent_node_list =[[]]
parent_node_list[0].append(root)
# 다음 Level 부터 살펴보면서 왼쪽/오른쪽 자식노드를 확인하고 넣는다.
for level in range(1, len(level_array)):
parent_node_list.append([])
for data in level_array[level]:
x = data[0]
value = data[1]
# 바로 위의 Level을 본다.
for parent_node in parent_node_list[level -1]:
# x 좌표가 left_bound 보다 크고 부모 노드보다 작은 위치라면 left node
if parent_node.left_bound <= x and parent_node.x > x:
now_node = Node(x, value, parent_node.left_bound, parent_node.x)
parent_node.left_node = now_node
parent_node_list[level].append(now_node)
break
# x 좌표가 right_bound 보다 작고, 부모 노드보다 큰 위치라면 right node
elif parent_node.right_bound >= x and parent_node.x < x:
now_node = Node(x, value, parent_node.x, parent_node.right_bound)
parent_node.right_node = now_node
parent_node_list[level].append(now_node)
break
preorder(root) # 전위 순회
postorder(root) # 후위 순회
return [preorder_result, postorder_result] |
