자료구조와 알고리즘 복습

오늘 알고리즘 박살낸다.

백준 1620번

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

포켓몬 문제

import sys

n, m = map(int, input().split())
li = []

for _ in range(n):
    li.append(input())

for _ in range(m):
    problem = sys.stdin.readline().rstrip('\n')
    if problem.isnumeric():
        problem = int(problem) - 1
        print(li[problem])
    else:
        print(li.index(problem) + 1)

결과(실패)

일단, 바로 생각난 python list를 이용해서 제출해봤으나,
예상대로 시간 초과

다음은 트리를 이용한 문제풀이

import sys


class Node:
    def __init__(self, data=None, num=None):
        self.data = data
        self.num = num
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None
        self.size = 0

    def find_min(self):
        node = self.root
        while node.left:
            node = node.left
        return node

    def find_max(self):
        node = self.root
        while node.right:
            node = node.right
        return node

    def insert(self, data, num):
        current = self.root
        pre_crt = self.root

        if current is None:
            self.root = Node(data, num)
            return

        while current:
            pre_crt = current
            if current.data > data:
                current = current.left
            else:
                current = current.right
        if pre_crt.data > data:
            pre_crt.left = Node(data=data, num=num)
        else:
            pre_crt.right = Node(data=data, num=num)

    def search(self, rqst):
        node = self.root
        while node:

            if node.data == rqst:
                return node.num
            elif node.data > rqst:
                node = node.left
            else:
                node = node.right
        return None

    def traverse(self, node):
        if node:
            self.traverse(node.left)
            print(node.data, end='')
            self.traverse(node.right)


t = Tree()
n, m = map(int, input().split())
li = []
for i in range(1, n+1):
    a = sys.stdin.readline().rstrip('\n')
    li.append(a)
    a = a.upper()
    t.insert(data=a, num=i)

for _ in range(m):
    problem = sys.stdin.readline().rstrip('\n')

    if problem.isnumeric():
        problem = int(problem) - 1
        print(li[problem])
    else:
        print(t.search(problem.upper()))

결과(트리 이용)

'input말고 readline을 사용하면 속도가 더 빨라진다' 라고 하지만 아직 속도의 차이를 체감할만한 예제를 접하지 않았다.

위의 리스트의 경우에는 어느 부분에 문제가 있어서 제한된 속도를 초과 했는 지 알 수 없다. 지금은 list 내부 함수 index가 느리다고 추정할 뿐이다.

이번 예제를 통한 중요한 학습으로 생성자에 변화를 주었을 때, 기존의 코딩의 매개변수에 주의할 필요가 있다는 것이다. Node의 생성자에 num을 기본 매개변수로 추가하면서 논리적 오류가 생겼지만, syntax error를 발생하진 않아 찾아내기 힘들었다. 내 생각에 이런 경우를 대비해서 IDE에서 제공한 툴이 있겠지만 의식적으로 생각하고 있어야 함을 느꼈다.

+추가 : '이 문제를 왜 트리를 이용해야 했는가?'에서 트리의 장점을 알 수 있다. sort할 필요없이 tree에 insert만으로도 정렬이 가능하여 search할 수 있기 때문이다.

백준 17219

비밀번호 찾기
(시간이 있어서 추가로 한 문제 더)

import sys

I = sys.stdin.readline
a, b = I().split()
d = {}
for i in [0]*int(a):
    s, p = I().split()
    d[s] = p
print("\n".join([d[i.strip()]for i in sys.stdin]))

우수 코딩

감명 깊었던 정답 코딩. 원래 코딩은 띄어쓰기와 줄 바꿈도 없어서 처음에 이해조차 못했다.
sys.stdin만 쓸 수 있다는 것을 처음 알았다. ( 근데 왜 난 ^z로 입력 중단이 안되는 건지 모르겠다. )
2번째 줄처럼 함수를 편한 변수로 선언하는 것도 인상깊었다.
가장 인상 깊었던 것은 join과 list comprehension을 통한 저 한 줄짜리 표현식.

그리고 거품낀 내 코딩

import sys


class Node:
    def __init__(self, homepage=None, password=None):
        self.homepage = homepage
        self.password = password
        self.left = None
        self.right = None


class Tree:
    def __init__(self):
        self.root = None
        self.size = 0

    def find_min(self):
        node = self.root
        while node.left:
            node = node.left
        return node

    def find_max(self):
        node = self.root
        while node.right:
            node = node.right
        return node

    def insert(self, homepage, password):
        current = self.root
        pre_crt = self.root

        if current is None:
            self.root = Node(homepage, password)
            return

        while current:
            pre_crt = current
            if current.homepage > homepage:
                current = current.left
            else:
                current = current.right
        if pre_crt.homepage > homepage:
            pre_crt.left = Node(homepage=homepage, password=password)
        else:
            pre_crt.right = Node(homepage=homepage, password=password)

    def search(self, rqst):
        node = self.root
        while node:

            if node.homepage == rqst:
                return node.password
            elif node.homepage > rqst:
                node = node.left
            else:
                node = node.right
        return None

    def traverse(self, node):
        if node:
            self.traverse(node.left)
            print(node.homepage, end='')
            self.traverse(node.right)


t = Tree()
n, m = map(int, input().split())

for _ in range(n):
    a, b = sys.stdin.readline().rstrip('\n').split()
    t.insert(homepage=a, password=b)

for _ in range(m):
    problem = sys.stdin.readline().rstrip('\n')

    print(t.search(problem))

결과

트리를 적용할 예제이기에 그냥 했지만, 문제를 처음 봤을 때는 딕셔너리가 적합하다고 생각했다. 하지만 python list의 index()와 마찬가지로 딕션너리의 key 또한 시간이 오래 걸릴 것이라 생각하여 트리를 사용하는 것이 더 빠를 것이라 예상했다. 결과는 딕션너리가 압도적으로 빨랐다.

숙련자의 코딩을 보고 지적 섹시함을 느꼈다.