문제 풀이 코드

import heapq

def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)  #1 
    while True:
        answer += 1
        heapq.heappush(scoville,heapq.heappop(scoville) + heapq.heappop(scoville) * 2)  #2
        if scoville[0] >= K:  #3
            return answer
        elif len(scoville) <= 1:
            return -1

#1

기존 scoville배열을 heap 자료구조로 변경시킴 (O(N))

#2

맨 앞 + (앞에서 두번째 X 2) 를 heap queue에 다시 집어넣음

#3

만약 가장 작은 인자가 K보다 크다면 섞은 횟수 반환

메타클래스에 대해 알아보기 이전에 파이썬의 데이터 모델에 대한 이해가 필요하다.

파이썬에서 모든 것은 데이터를 추상화 한 객체로 이루어져 있다.
또한, 파이썬의 객체는 아이덴티티, 값, 타입을 가지고 있다.

아이덴티티 (id)

id() 함수를 통해 얻을 수 있으며 객체의 수명동안 유일하고 불변함이 보장되는 정수다.

값 (value)

객체의 타입에 따라 불변할 수 있고 가변할 수도 있다. ex)tuple : 불변, list : 가변

타입 (type)

객체가 지원하는 연산들과 그 타입의 객체가 가질 수 있는 값(ex) int : 1, list : [1,2])들을 통해 객체의 특성을 정의한다. 객체의 타입은 type()을 통해 얻을 수 있으며, 불변하다.

여기서 말한 타입과 같이 파이썬의 모든 객체들은 어떠한 타입에 의해 정의된다.

파이썬의 type() 빌트인 함수를 사용하면 객체의 타입을 알 수 있다.

class Test:
    pass
t = Test()
type(t)
# <class '__main__.Test'>

def hello():
    pass
type(hello)
# <class 'function'>

type(1)
# <class 'int'>

위 예제를 보면 Test 클래스의 인스턴스인 tTest가 타입이고, hello 함수는 function이 타입이며, 정수 1은 int가 타입이다.

그렇다면, Test 클래스의 타입은 존재할까?

class Test:
    pass
type(Test)
# <class 'type'>

놀랍게도, Test 클래스 객체의 타입이 존재한다.
여기서 출력된 typeTest 클래스의 메타 클래스라고 하며, 인스턴스로 클래스를 가진다.

그러면 메타클래스는 무슨 용도로 사용하는 걸까?

그전에 몇가지 메타클래스의 매직 메소드에 대해 알아보자

class TestMeta(type):
    def __prepare__(mcs, *args, **kwarg): # 메타 클래스가 결정되었을 때 (mro가 구성된 후) 클래스 정의를 위해 호출된다.
        # mcs = metaclass
        print("__prepare__()")
        return super.__prepare__(mcs, *args, **kwarg)

    def __new__(mcs, *args, **kwargs):  # 클래스를 생성 할 때 호출됨
        # mcs = metaclass
        print("__new__()")
        return super().__new__(mcs, *args, **kwargs)

    def __init__(cls, *args, **kwargs):  # 클래스가 생성 된 후 호출됨
        print("__init__()")
        super().__init__(*args, **kwargs)

    def __call__(cls, *args, **kwargs):  # 클래스의 인스턴스를 생성할 때 호출됨
        print("__call__()")
        return super().__call__(*args, **kwargs)


class Test(metaclass=TestMeta):
    pass

# __prepare__()
# __new__()
# __init__()

t = Test()
# __call__()

위 코드를 보면 __prepare__, __new__, __init__, __call__ 메소드를 작성하고 사용하는 것을 볼 수 있다.

  • __prepare__ 메소드는 메타 클래스가 결정되었을 때 호출되며, 클래스의 네임 스페이스를 준비한다.
  • __new__ 메소드는 클래스 객체를 생성 할 때 호출된다.
  • __init__ 메소드는 클래스가 생성 된 후 호출되어 클래스를 초기화 한다.
  • __call__ 메소드는 클래스의 인스턴스를 생성 할 때 호출 된다.

이 매직 메서드를 가지고 무슨 일을 할 수 있을까?

싱글톤 패턴 구현

싱글톤 패턴은 클래스의 인스턴스화를 항상 하나의 개체로만 제한하는 설계 패턴이다.
구현해 보자면

class SingletonMeta(type):
    _instances = {}

    def __call__(cls, *args, **kwargs):
        if cls not in cls._instances:
            cls._instances[cls] = super().__call__(*args, **kwargs)
        return cls._instances[cls]


class SingletonClass(metaclass=SingletonMeta):
    pass

sl1 = SingletonClass()
sl2 = SingletonClass()

print(id(sl1))
# 1877212284048
print(id(sl2))
# 1877212284048

인스턴스 생성에 관여하는 __call__()메소드를 오버라이딩 해서 클래스를 key로 두고 인스턴스를 value로 만들어 클래스당 하나의 인스턴스를 가지도록 했다.

애트리뷰트 검증

DRF의 ModelSerializer 에는 내부 Meta 클래스가 없다면 오류를 일으킨다. 이에 대한 오류 검증을 DRF에서는 get_fields() 메소드에 구현해 두었는데, 이를 메타 클래스로 검증 할 수 있을 것 같다.

def get_fields(self):
    ...

    assert hasattr(self, 'Meta'), (
        'Class {serializer_class} missing "Meta" attribute'.format(
            serializer_class=self.__class__.__name__
        )
    )
    ...

위 코드는 클래스 내부에 Meta 애트리뷰트가 있는지 확인하는 코드이다. 이를 메타클래스로 검증하는 코드를 짜보자

class ModelSerializerMetaclass(SerializerMetaclass):
    def __new__(mcs, *args, **kwargs):
        name, bases, namespace = args
        if name not in ("ModelSerializer","HyperlinkedModelSerializer"):
            mcs._check_meta(name,namespace)

        return super().__new__(mcs, *args, **kwargs)

    def _check_meta(name,namespace):
        if not namespace.get("Meta", None):
            raise Exception(f'Class {name} missing "Meta" attribute')
        return


class ModelSerializer(Serializer, metaclass=ModelSerializerMetaclass):
    pass

https://github.com/encode/django-rest-framework/pull/7970

아이디어

def solution(phone_book):
    for a in phone_book:
        for b in phone_book:
            if a.startswith(b) and a != b:
                return False
    return True

그냥 문제 보자마자 이 코드가 생각났다.
물론 정확성 테스트는 그냥 통과하는데 효율성 테스트에서 막힌다.

다른 방법을 생각해야 했다.

제한 사항을 확인하자.


phone_book의 길이가 1,000,000 이하라고 한다.
최대 O(n log n) 으로 풀어야 한다.

문제 풀이 코드

def solution(phone_book):
    phone_book.sort()  # 1
    for a,b in zip(phone_book, phone_book[1:]): # 2
        if b.startswith(a):
            return False
    return True

#1

문자열 정렬로 접두어 번호가 비교되는 번호의 앞에 오도록 한다.

#2

바로 앞, 뒤만 체크하며 지나가 시간 복잡도가 줄어든다 O(N)

아이디어

  1. 대기열의 첫번째가 나머지 보다 크다면 대기열에서 삭제 (인쇄)
    => 대기열의 첫번째 보다 나머지가 작지 않다면 대기열 맨 뒤로 보냄

  2. 하나가 인쇄 될 때 마다 answer += 1

  3. 만약 인쇄 된 문서의 순서(i)가 location과 일치한다면 answer return

  4. 하나라도 첫번째 보다 크다면 대기열 맨 뒤로 보냄

    문제 풀이 코드

    def solution(priorities, location):
     answer = 0
     priorities = [(i,value) for i, value in enumerate(priorities)]  # 1
    
     while True:
         move_to_back = False
    
         for priority in priorities:  # 2
             if priorities[0][1] < priority[1]:
                 move_to_back = True
                 break
    
         if move_to_back:  # 3
             priorities.append(priorities.pop(0))
         else: # 4
             answer += 1
             if priorities[0][0] == location:
                 return answer
             priorities.pop(0)

    1

    초기 location을 기억하기 위해 데이터 구조를 [index, value]로 변경

    2

    하나라도 맨 앞의 문서보다 중요도가 높다면 move_to_back = True

    3

    하나라도 맨 앞의 문서보다 중요도가 높다면 맨 앞의 문서를 맨 뒤로 이동시킴

    4

    맨 앞의 문서의 중요도가 가장 높으면 인쇄(대기열에서 삭제)하며 몇번째로 실행되었는지 알기 위해 answer에 +1을 해준다.
    또한, 내가 찾는 문서라면 answer을 반환한다

OOP를 공부하다 보면 가끔 1급 객체(first-class citizen) 혹은 1급 함수에 대한 언급을 볼 수 있다.

이것에 대한 지식이 없을때 항상 이 두가지가 궁금했다.

  1. 1급 객체란 무엇일까?
  2. 함께 언급 되는 고차 함수는 무엇일까?

두가지만 알아보자

그런데 설명하기 앞서, 1급 객체1급 함수는 같은 개념이란 것을 알아두자

1. 1급 객체란 무엇일까?

1급 객체는 3가지 조건을 모두 충족하는 객체를 말한다.

1. 변수나 데이터에 할당 할 수 있어야 한다.
2. 객체의 인자로 넘길 수 있어야 한다.
3. 객체의 반환값으로 반환할 수 있어야 한다.

위키피디아 링크

간단히 말하자면, Object로서의 특성을 모두 지닌 것1급 객체라고 부른다.

Python의 함수는 위 세가지 조건을 모두 충족한다.

그렇기 때문에 Python의 함수는 일급 객체라고 할 수 있다.

참고로, Python의 모든 것은 객체이다.

예시를 보면서 이해해보자

# 1. 변수나 데이터에 할당 할 수 있어야 한다.
def print_hello():
    print("hello!")

a = print_hello  # print_hello 함수를 a라는 변수에 저장
a()
# hello!
# 2. 객체의 인자로 넘길 수 있어야 한다.
def introduce(name):
    return "hello, my name is" + name

def goodbye(name):
    return "bye bye, " + name


def who_i_am(func, name):
    return func(name)

who_i_am(introduce, "hanbin")
# hello, my name is hanbin
who_i_am(goodbye, "hanbin")
# bye bye, hanbin
# 3. 객체의 반환값으로 반환할 수 있어야 한다.
def test_hasher(data):
    return "hashed" + data

def get_hasher():
    return test_hasher  # test_hasher함수를 반환한다.

hasher = get_hasher()
hashed_data = hasher("hanbin")
print(hashed_data)
# hashed hanbin

2. 고차 함수(higher-order function)?

1. 객체의 인자로 넘길 수 있어야 한다.
2. 객체의 반환값으로 반환할 수 있어야 한다.

두가지 조건을 충족하는 함수를 말한다.

문제 풀이 코드

def solution(bridge_length, weight, truck_weights):
    # sum(다리를 건너는 트럭) + truck_weights[0] 가 weight이 안넘으면
    # 다리를 건너는 트럭.append(truck_weights[0])
    # 다리를 건너는 트럭[0][1] 을 시간이 지날때 마다 += 1 해줌
    # 다리를 건너는 트럭[0][1] 이 weight보다 크거나 같으면
    # 다리를 건너는 트럭[0] 을 다리를 지난 트럭으로 이동
    # 위 과정을 반복
    time = 0
    truck_weights = list(map(lambda x : [int(x),0],truck_weights))  #1
    current_bridge = []

    while True:
        time += 1
        current_bridge = list(map(lambda x : [x[0],x[1] + 1],current_bridge))  #2

        if len(current_bridge) > 0:
            if current_bridge[0][1] > bridge_length:  # 3
                del current_bridge[0]

        if len(truck_weights) > 0:
            if sum(map(lambda x : x[0] ,current_bridge)) + truck_weights[0][0] <= weight:  # 4
                truck = truck_weights.pop(0)
                current_bridge.append([truck[0],truck[1] + 1])

        if len(current_bridge) +  len(truck_weights) <= 0:
            break
    return time

#1

truck_weights 의 데이터 구조를 [무게, 현재 위치] 구조로 잡음
현재 위치 : 다리를 어느정도 건넜는가 (대기 상태이면 0)

#2

시간이 지날 때 마다 트럭이 다리를 1만큼 이동함 (다리 위에 올라가 있는 트럭만)

#3

트럭이 다리를 모두 건넜다면 제거해줌

#4

다리에 트럭을 더 올릴수 있다면 올림

오류 내용


윈도우 환경에서 실행할 때는 잘 돌아갔는데 Docker에 올려 리눅스 환경에서 실행할 때 위와 같은 에러가 발생했다.

우선 해결 방법은 maxsize를 지정해 주면 된다.
ex) @lru_cache(maxsize=128)

왜 이러지?

찾아봤는데 윈도우와 리눅스 환경의 차이는 아니고 파이썬 버전에 차이가 있었다.

Python 3.7
Python 3.8

Python 3.8 의 517번째줄 주석을 보면 "user_fuction 이 maxsize 인수로 직접적으로 전달되었다." 라는 말이 있다.

Python 3.8에서는 데코레이터의 wrap function이 maxsize로 전달되어 버렸을 때의 데이터 처리 과정이 있지만 Python 3.7에는 존재하지 않는다.

그렇기 때문에 maxsize를 지정해 주지 않으면 wrap function이 maxsize로 전달되어 버려 예외가 일어나는 것이다.

문제 풀이 코드

function solution(progresses, speeds) {
    var answer = [];
    var count = 0;
    var time = 0;  // #1
    while(progresses.length > 0){
        if ((progresses[0] + speeds[0] * time) >= 100 ){  // #2
            count += 1;
            progresses.splice(0,1);
            speeds.splice(0,1);
            time -= 1;  // #3
        } else {
            if (count > 0){
                answer.push(count);  // #4
                count = 0;
            }
        }
        time += 1;
    }
    answer.push(count);
    return answer;
}

FIFO 구조에서 착안해서 코딩했다.

#1

하루가 지날때 마다 시간을 기록하는 변수

#2

진행도 + 작업 속도 X 시간 이 100보다 크면 count += 1

#3

같은 날에 이미 끝난 작업을 체크하기 위해 time -= 1

#4

더이상 끝난 다음 작업이 없으면 answer에 push 함

+ Recent posts