Assignment 3

Assignment 3

이제까지 혼자만의 힘으로 풀어 굉장히 많은 시간을 소요했었는데 앞으로는 참고를 하며 이해를 하고 빠르게 넘어가야 할 것같다. 목표한 바보다 일정이 늦어졌기에.

1번 문제는 Phone book을 다루는 문제이다.

Input format :
N (number of queries)
queries (type number [name])

Output format :
results of each find query

첫번째 예시를 보면 처음에 등장하는 정수인 12가 12개의 query를 받을 준비가 됨을 알려주며 이후 add, find, del 의 명령의 동작에 맞게 작동한다. 그리고 find 명령마다 출력을 내보내준다.

# python3

class Query:
    def __init__(self, query):
        self.type = query[0]
        self.number = int(query[1])
        if self.type == 'add':
            self.name = query[2]


def read_queries():
    n = int(input())
    return [Query(input().split()) for i in range(n)]


def write_responses(result):
    print('\n'.join(result))


def process_queries(queries):
    result = []
    # Keep list of all existing (i.e. not deleted yet) contacts.    contacts = []
    for cur_query in queries:
        if cur_query.type == 'add':
            # if we already have contact with such number,            # we should rewrite contact's name            for contact in contacts:
                if contact.number == cur_query.number:
                    contact.name = cur_query.name
                    break                else:  # otherwise, just add it                    contacts.append(cur_query)
        elif cur_query.type == 'del':
            for j in range(len(contacts)):
                if contacts[j].number == cur_query.number:
                    contacts.pop(j)
                    break        else:
            response = 'not found'            for contact in contacts:
                if contact.number == cur_query.number:
                    response = contact.name
                    break            result.append(response)
    return result


if __name__ == '__main__':
    write_responses(process_queries(read_queries()))

기본코드이며 Query 클래스를 통해 입력받은 쿼리의 요소들을 분리하여 처리가 가능하고 read_queries, write_responses를 통해 입력을 받고 출력할 것들을 반환하게 된다. 마지막인 process_queries를 direct addressing을 통해 최적화를 진행해야 한다.

# python3

class Query:
    def __init__(self, query):
        self.type = query[0]
        self.number = int(query[1])
        if self.type == 'add':
            self.name = query[2]


def read_queries():
    n = int(input())
    return [Query(input().split()) for i in range(n)]


def write_responses(result):
    print('\n'.join(result))


def process_queries(queries):
    result = []
    # Keep list of all existing (i.e. not deleted yet) contacts.    contacts = [None] * (10**7)
    for cur_query in queries:
        if cur_query.type == 'add':
            contacts[cur_query.number] = cur_query.name

        elif cur_query.type == 'del':
            contacts[cur_query.number] = None
        else:
            if contacts[cur_query.number] is None:
                result.append('not found')
            else:
                result.append(contacts[cur_query.number])
    return result


if __name__ == '__main__':
    write_responses(process_queries(read_queries()))

제약조건에 명시된 것처럼 contacts를 10^7으로 고정시켜놓고 이후 index를 통해 접근하여 바로 연산을 하는 것이 for문을 통해 작업하는 것보다 훨씬 빠를 것이다.

2번째는 chaining하는 문제이며 수식과 함께 미리 상수를 주었다.

p = 1 000 000 007, x = 263

Input format :
m (the number of buckets)
N (the number of queries)
queries

Output format :
result of  find/check queries

이번에도 예시를 보면 쉽게 이해가능한데 첫번째 예시를 보면 받은 문자들에 대해 ASCII코드로 변환하고 이를 x^i과 연산 후 p로 modulo연산을 한 결과에 m으로 modulo한 값을 가지고 chaining을 한 것을 볼 수 있다. 이후에는 find/check에 대한 결과값들을 보내주게 된다.

추가적인 예시들까지 보고 overflow를 조심하라는 지시문도 확인하였다.

# python3
class Query:

    def __init__(self, query):
        self.type = query[0]
        if self.type == 'check':
            self.ind = int(query[1])
        else:
            self.s = query[1]


class QueryProcessor:
    _multiplier = 263    _prime = 1000000007
    def __init__(self, bucket_count):
        self.bucket_count = bucket_count
        # store all strings in one list        self.elems = [None] * bucket_count

    def _hash_func(self, s):
        ans = 0        for c in reversed(s):
            ans = (ans * self._multiplier + ord(c)) % self._prime
        return (ans % self.bucket_count + self.bucket_count) % self.bucket_count

    def write_search_result(self, was_found):
        print('yes' if was_found else 'no')

    def write_chain(self, chain):
        if chain != None:
            print(' '.join(chain))
        else:
            print(' ')

    def read_query(self):
        return Query(input().split())

    def process_query(self, query):
        if query.type == "check":
            self.write_chain(self.elems[query.ind])
        else:
            hash_key = self._hash_func(query.s)
            if query.type == 'find':
                if self.elems[hash_key] != None and (query.s in self.elems[hash_key]):
                    self.write_search_result(True)
                else:
                    self.write_search_result(False)
            elif query.type == 'add':
                if self.elems[hash_key] == None:
                    self.elems[hash_key] = [query.s]
                else:
                    if query.s not in self.elems[hash_key]:
                        self.elems[hash_key].insert(0, query.s)
            else:
                if self.elems[hash_key] != None and query.s in self.elems[hash_key]:
                    self.elems[hash_key].remove(query.s)
                    if len(self.elems[hash_key]) == 0:
                        self.elems[hash_key] = None
    def process_queries(self):
        n = int(input())
        for i in range(n):
            self.process_query(self.read_query())

if __name__ == '__main__':
    bucket_count = int(input())
    proc = QueryProcessor(bucket_count)
    proc.process_queries()

check일 경우에는 해당 ind에 해당하는 chain을 출력하도록 하고 이외의 경우엔 find, add, del type에 따라 연산을 진행해 주도록하면 될 것이다.

3번째 문제는 hash substring에 해당하는 find pattern in text에 관한 문제이다. Rabin-Karp 알고리즘을 활용해 해결하라는 지시가 있다.

Input format :
P (pattern)
T (text)

Output format :
position (all the occurrences of P in T, ascending order)

첫번째 예시를 보자면 P = aba, T = abacaba이므로 해당 결과는 0 4가 나올 것이다.

# python3

def read_input():
    return (input().rstrip(), input().rstrip())


def print_occurrences(output):
    print(' '.join(map(str, output)))


def get_occurrences(pattern, text):
    return [
        i 
        for i in range(len(text) - len(pattern) + 1) 
        if text[i:i + len(pattern)] == pattern
    ]


if __name__ == '__main__':
    print_occurrences(get_occurrences(*read_input()))

기초 코드상으로는 기본적인 기능으로 구현이 되어있고 양이 방대해질수록 연산시간이 더 많이 걸리게 된다.

# python3import random

def read_input():
    return (input().rstrip(), input().rstrip())

def print_occurrences(output):
    print(' '.join(map(str, output)))

def hash_func(s, p, x):
    ans = 0    for c in reversed(s):
        ans = ((ans * x + ord(c)) % p + p) % p
    return ans

def precompute_hashes(pattern, text, p, x):
    result = [None] * (len(text) - len(pattern) + 1)
    S = text[(len(text)-len(pattern)):len(text)]
    result[len(text)-len(pattern)] = hash_func(S, p, x)

    y = 1    for i in range(1, len(pattern) + 1):
        y = (y * x) % p
    for i in range(len(text) - len(pattern) - 1, -1, -1):
        result[i] = (x * result[i+1] + ord(text[i]) - y * ord(text[i + len(pattern)])) % p

    return result

def get_occurrences(pattern, text):
    _prime = 1000000007    x = random.randint(0, _prime)
    hashes = precompute_hashes(pattern, text, _prime, x)
    result = []
    pHash = hash_func(pattern, _prime, x)
    for i in range(0, len(text) - len(pattern) + 1):
        if pHash != hashes[i]:
            continue        if text[i:i + len(pattern)] == pattern:
            result.append(i)
    return result

if __name__ == '__main__':
    print_occurrences(get_occurrences(*read_input()))

hash_func에서는 chaining을 위한 연산값에 대한 수식이 들어가며 precompute_hashes에서는 hash value로 대응하는 역할을 한다. get_occurrences에서는 hash value를 먼저 비교 후 동일 값에 대해서만 다시 확인하여 반환해주는 순서로 구성되어 있다.

아래 출처에 있는 글을 참고하였으며 굉장히 깔끔하게 정리되어 있는 것을 보고 감탄하였다.

출처 : https://medium.com/@ltanphat/course-2-data-structure-part-3-hash-11ccf163cb09