acmicpc.net 1991(이진 트리), 4256(이진 트리), 11441, 10825

https://www.acmicpc.net/problem/1991

이진 트리를 구현하면 된다. 근데 일반적인 이진 트리와 조금 다르게 잘 구현하면 된다. 숏코딩을

보면 파이썬으로 내 코드보다 1/7길이로 구현해놨던데 그게 가능한지 궁금하다... 

# -*- encoding: cp949 -*-
from __future__ import print_function
class node:
    def __init__(self, data):
        self.left = 0
        self.right = 0
        self.data = data

class binarytree:
    def __init__(self):
        self._node = node(0)
    def insert(self, data):
        self.cur_node = self._node
        if self.cur_node.data==0:
            self.cur_node.data = data[0]
            self.cur_node.left = node(data[1])
            self.cur_node.right = node(data[2])
        else:
            find(self.cur_node, data)

def find(cur_node, data):
    if type(cur_node) is not int and cur_node.data == data[0]:
        cur_node.left = node(data[1])
        cur_node.right = node(data[2])
    elif type(cur_node) is not int and cur_node.data != data[0]:
        find(cur_node.left, data)
        find(cur_node.right, data)

def _pre(b):
    global ans
    if (type(b) is not int) and b.data !=0 and b.data!='.':
        print(b.data,end='')
        _pre(b.left)
        _pre(b.right)

def _in(b):
    global ans
    if (type(b) is not int) and b.data !=0 and b.data!='.':
        _in(b.left)
        print(b.data,end='')
        _in(b.right)

def _post(b):
    global ans
    if (type(b) is not int) and b.data !=0 and b.data!='.':
        _post(b.left)
        _post(b.right)
        print(b.data,end='')

b_tree = binarytree()
n = int(raw_input())
for i in xrange(n):
    t_node = raw_input().split()
    b_tree.insert(t_node)

_pre(b_tree._node)
print()
_in(b_tree._node)
print()
_post(b_tree._node)
print()

---

딕셔너리로 구현한 간단한 이진 트리.

# -*- encoding: cp949 -*-
def _pre(tree, c):
    global ret
    if c=='.': return
    ret += c
    _pre(tree, tree[c][0])
    _pre(tree,tree[c][1])

def _in(tree, c):
    global ret
    if c=='.': return
    _in(tree, tree[c][0])
    ret += c
    _in(tree,tree[c][1])

def _post(tree, c):
    global ret
    if c=='.': return
    _post(tree, tree[c][0])
    _post(tree,tree[c][1])
    ret += c

tree={}
n=input()
for k in xrange(n):
    node = raw_input().split()
    tree[node[0]] = [node[1], node[2]]

for f in [_pre, _in, _post]:
    ret = ''
    f(tree,'A')
    print ret

재귀적인 방법이 아닌 iterative한 방법.

# -*- coding: utf-8 -*-

def preorder(root):
    visited = [0 for i in xrange(n+1)]
    stack = [root]
    answer = ''

    while stack:
        p = stack.pop()
        if visited[ord(p)-65] == 0:
            visited[ord(p)-65] = 1
            answer += p
        for child_node in [tree[p][1], tree[p][0]]:
            if child_node != '.' and visited[ord(child_node)-65] == 0:
                stack.append(child_node)
    print answer


def inorder(root):
    stack = [root]
    answer = ''

    while True:
        while stack:
            node = stack[-1]
            if node:
                left = tree[node][0]
                if left == '.':
                    break
                stack.append(left)

        while stack:
            node = stack.pop()
            answer += node
            if tree[node][1] != '.':
                stack.append(tree[node][1])
                break

        if not stack:
            break

    print answer


def postorder(root):
    visited = [0 for i in xrange(n + 1)]
    stack = [root]
    answer = ''

    while stack:
        p = stack.pop()
        if visited[ord(p) - 65] == 0:
            visited[ord(p) - 65] = 1
            answer += p
        for child_node in [tree[p][0], tree[p][1]]:
            if child_node != '.' and visited[ord(child_node) - 65] == 0:
                stack.append(child_node)
    print answer[::-1]

tree = {}
n = input()
for i in xrange(n):
    node = raw_input().split()
    tree[node[0]] = [node[1], node[2]]

preorder('A')
inorder('A')
postorder('A')

---

https://www.acmicpc.net/problem/4256

전위 순회와 중위 순회로 후위 순위를 구하는 문제.

# -*- encoding: cp949 -*-
def post(_pre, _in):
    global ans
    if not _pre: return
    root = _pre[0]
    if type(_in) is int:
        _in = [_in]
    l = _in.index(root)
    r = len(_pre) - 1 - l
    post(_pre[1:l+1], _in[:l])
    post(_pre[l+1:], _in[l+1:])
    ans += str(root)+' '

for t in xrange(input()):
    n = input()
    _pre = map(int,raw_input().split())
    _in = map(int,raw_input().split())
    ans = ''
    post(_pre, _in)
    print ans[:-1]

https://www.acmicpc.net/problem/11441

합 구하는 문제이다. 그냥 풀면 시간초과가 나온다. 질문을 검색해봤는데 어떤분이 좋은 댓글을 

달아주셨다. 기본적인거 같은데 여태까지 프로그래밍 하면서 이것도 몰랐다니....

{A1, A2, ... , An}이 있을 때, Si = A1 + A2 + ... + Ai라고 하면,

Ai + Ai + 1 + ... + Aj - 1 + Aj는 Sj - Si - 1로 표현할 수 있다는 의미입니다.

n = input()
a = map(int,raw_input().split())
s_list = [0 for i in xrange(n+1)]
s_list[1] = a[0]
for i in xrange(2,n+1):
    s_list[i] = s_list[i-1]+a[i-1]
for m in xrange(input()):
    i,j = map(int,raw_input().split())
    print s_list[j] - s_list[i-1]

https://www.acmicpc.net/problem/10825

# -*- encoding: cp949 -*-
s = [raw_input().split()for i in xrange(input())]
s = map(lambda x:map(int,x[0]+x[1:4]))
s = sorted(s, key=lambda x:(-int(x[1]),int(x[2]),-int(x[3]),x[0]))
print '\n'.join(map(lambda x:x[0],s))