2018 kakao blind recruitment 길 찾기 게임

import operator
import sys
sys.setrecursionlimit(10**6)
def solution(nodeinfo):
    answer = []
    # idx를 기억하기 위해 idx를 포함하는 리스트로 변형
    nodeinfo = [[idx+1, x[0], x[1]] for idx, x in enumerate(nodeinfo)]
    # y좌표를 기준으로 정렬
    nodeinfo = sorted(nodeinfo, key=operator.itemgetter(2))
    # print(nodeinfo)
    bt = Binarytree()
    for index in nodeinfo[::-1]:
        bt.insert(index)
    answer.append(bt.preorder(bt.root))
    answer.append(bt.postorder(bt.root))
    return answer
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
class Binarytree:
    def __init__(self):
        self.root = None
    def insert(self, data):
        self.root = self._insert_value(self.root, data)
        return self.root is not None
    def _insert_value(self, node, data):
        if node is None:
            node = Node(data)
        else:
            if data[1] < node.data[1]:
                node.left = self._insert_value(node.left, data)
            else:
                node.right = self._insert_value(node.right, data)
        return node
    def preorder(self, node):
        if node == None:
            return []
        else:
            return [node.data[0]]+self.preorder(node.left)+self.preorder(node.right)
    def postorder(self, node):
        if node == None:
            return []
        else:
            return self.postorder(node.left)+self.postorder(node.right)+[node.data[0]]
        

 

BinaryTree를 이용해서 풀었다.

풀이에서는 x의 범위를 지정해 줘야 된다고 하던데 그냥 y값을 기준으로 정렬해서 x값만 비교해가며 넣으면 되는 거 아닌가...? 싶어서

반신반의하며 그렇게 해 봤더니 됐다!

그리고 두개 정도의 문제에서 런타임 에러가 나길래 뭘까 하다가 혹시 재귀함수의 depth 문제 때문인가 싶어서 인터넷을 뒤져 depth를 늘려주는 라인을 추가했다. (출처)

Binarytree 만드는 코드는 studynote라는 블로그를 참고했다.

여기서 바꾼 건 preorder와 postorder에서 리턴하는 방식 뿐이다.

list(node.data[0])는 정수형은 iterable하지 않기 때문에 안 된다는 에러가 나서 [node.data[0]]으로 바꿔주었다.

파이썬 자습서나 라이브러리 레퍼런스에서 list() 함수에 대해 다시 봐야겠다.

 

-

 

코딩테스트를 공부하면서 느끼는 건 리팩토링의 중요성....

예전에 문제해결기법 강의에서 교수님이 for i <- 이런 식으로 코드를 작성하게 되면 나중에 수정하게 될 때 좋지 않다고 해서 그 때부터 최대한 그 변수가 의미하는 것을 담도록 변수의 이름을 선언하고 있는데, 이게 정말 도움이 많이 되는 것 같다. (후에 소프트웨어공학개론에서 refactoring이라는 이름으로 배웠다.) 저번 방학 때 협업을 할 때도 여러 명이 같은 코드를 만질 때, 그리고 내 코드를 남에게 보여주며 설명해야 할 때 나조차도 내 코드가 가독성이 좋지 않으면 새로운 기분을 느꼈다. (...) 비단 남에게 보여주기 위해서뿐만 아니라, 나를 위해서도 리팩토링은 정말 중요한 것 같다. 어제 코딩테스트를 할 때는 시간과 압박감에 쫓겨 그러지 못했지만 (ㅠㅠ)

오늘보다 내일 더 잘할 거니까~~!