leetcode 146(lru 캐시 구현), 604(문자열 압축풀기 구현), 443(문자열 압축 구현)

146 https://leetcode.com/problems/lru-cache/

lru 캐시를 구현하는 문제이다. python 의 ordereddict은 딕셔너리지만 넣은 순서가 보장된다. 이걸 이용한다. 아래처럼 구현하면 모든 연산이 O(1)이다. pop과 popitem이 O(1)연산인가? 궁금해서 찾아봤더니 맞다고 한다.

from collections import OrderedDict

class LRUCache(object):

    def __init__(self, capacity):
        self.cache = OrderedDict()
        self.c = capacity
        self.cur_len = 0

    def get(self, key):
        if key not in self.cache:
            return -1
        v = self.cache.pop(key)
        self.cache[key] = v
        return v

    def put(self, key, value):
        if key in self.cache:
            self.cur_len -= 1
            del self.cache[key]
        elif self.cur_len == self.c:
            self.cur_len -= 1
            self.cache.popitem(last=False)
        self.cache[key] = value
        self.cur_len += 1

문제를 풀면서 ordereddict를 써도 되나? 하는 고민이 있었는데 이 코멘트를 보니 써도 괜찮을것같다. 번역해왔다.

I'm a software engineer who interviews candidates from time to time. Familiarity with APIs of and ability to identify and use appropriate data structures even if they are slightly more advanced wrappers around simpler structures is also an important skill in software engineering. It may be a good to clarify with the interviewer what they expect for the time allotted. For this particular problem, given a ~45-60 min round - I think I would totally accept an OrderedDict solution.
저는 종종 지원자들을 인터뷰하는 개발자입니다. API들에 익숙하고 적절한 자료구조들을 활용하는건 소프트웨어 공학에서 중요한 스킬입니다. 물론 이 자료구조들이 일반적인 자료구조들보다 조금 더 advanced하게 래핑되어있다고해도 말이죠. 이런것들을 활용하는건 인터뷰에 할당된 시간안에 문제의 의도대로 구현했는지 판별하기에 더 좋은것 같습니다. 대부분 이런 문제에 45~60분 정도의 시간이 주어지며, 제가 면접관이면 OrderedDict을 사용한 해답도 옳은 대답이라고 인정할 것입니다.

....

If a candidate does use the OrderedDict approach, a good follow up might be to ask them how they would implement a basic OrderedDict which will hopefully lead them to the doubly linked list + hash map approach and then maybe write some code for that depending on available time. I think it boils down to the time allocated for the problem + factoring in how much the candidate knows already vs how much they need to think of on the spot.

지원자가 OrderedDict을 사용해서 풀었으면 다음으로 물어보기 좋은 질문은 기본적인 OrderedDict을 어떻게 구현할수 있을까요? 입니다. 남은 시간안에 doubly linked list와 hash map을 사용해 접근하면 좋은 접근법이 될것 같습니다. 핵심은 할당된 시간안에 문제를 지원자가 이미 아는 지식으로 어떻게든 풀어내느냐, 또는 그 자리에서 얼마나 더 깊게 파고들어야 하느냐에 따른 차이인것 같습니다.

결론 : ordereddict 써도 된다. 다만 원리가 어떻게 되는지 알아두자. 

추가로 내가 ordereddict을 써도 되는지 고민했던 이유는 이게 파이썬에만 있는줄 알아서였다. 파이썬에만 있는걸 쓰면 cheating같은 개념이 되니까 고민했었는데 찾아보니까 자바에도 linkedhashmap이라는 순서가 보장된 해시맵이 있다. 그냥 써도 될것같다.

그냥 dictionary와 doubly linked list를 이용한 해법은

https://leetcode.com/problems/lru-cache/discuss/45926/Python-Dict-%2B-Double-LinkedList 에 있다.

그리고 파이썬 3.7부터는 기본 딕셔너리가 넣은 순서를 보장한다고 하기때문에 조금만 지나면 딱히 고민하지 않아도 될듯 싶다. https://www.flowdas.com/2018/01/23/dict-is-ordered.html

604 https://leetcode.com/problems/design-compressed-string-iterator/

압축된 문자열을 풀어내는걸 구현하는 문제이다. 정규식으로 문자, 반복되는 갯수를 가져온 후 구현한다.

import re

class StringIterator(object):

    def __init__(self, compressedString):
        self.str_list = []
        for s in re.findall('\w\d+', compressedString):
            self.str_list.append([s[0], int(s[1:])])

    def next(self):
        if not self.str_list:
            return ' '
        k = self.str_list[0][0]
        self.str_list[0][1] -= 1
        if self.str_list[0][1] == 0:
            self.str_list.pop(0)
        return k
    
    def hasNext(self):
        return True if self.str_list else False

443 https://leetcode.com/problems/string-compression/

솔직히 좋은 문제인지 모르겠다. 싫어요가 많은 이유가 이해가 간다. 이해가 안가는건 ['a', 'b', 'b']의 결과값은 ['a', '1', 'b', '2']가 아니라 ['a', 'b', '2'] 여야 한다는것과 10개 이상이 반복되면 ['a', '10']이 아니라 ['a', '1', '2']처럼 만들어야 한다.

class Solution(object):
    def compress(self, chars):
        i = 0
        _len = len(chars)
        while i < len(chars):
            c = 1
            j = i + 1
            while j < len(chars):
                if chars[i] == chars[j]:
                    c += 1
                else:
                    break
                j += 1
    
            c = list(str(c))
            if c == ['1']:
                chars[:] = chars[:i+1] + chars[j:]
                i += 1
            else:
                chars[:] = chars[:i+1] + c + chars[j:]
                i += (1 + len(c))