231124 - kakao2023 : Datetime+상대시간, 포화이진트리

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/150370

개인정보 수집 휴효기간(Datetime+상대시간)

from datetime import datetime, timedelta
from dateutil.relativedelta import relativedelta

def solution(today, terms, privacies):
    temp = dict()
    for t in terms:
        kind, month = t.split()
        temp[kind] = int(month)
    # print(temp)

    today = datetime.strptime(today, "%Y.%m.%d")
    # print(today)
    result = []
    for idx, p in enumerate(privacies):
        sign_day, kind = p.split()
        sign_day = datetime.strptime(sign_day, "%Y.%m.%d")
        delta = relativedelta(months = temp[kind])
        diff = sign_day + delta - timedelta(days=1)
        # print(diff)

        if diff < today:
            result.append(idx+1)

    answer = result
    return answer

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/150369

택배 배달과 수거하기

배달 스택에서 가장 위에 위치한 원소는 배달할 택배가 남아있는 집 중 가장 멀리 있는 집입니다.

이번에 배달 가능한 개수는 cap으로 시작해, 배달 스택에서 꺼내는 순서대로 배달할 택배 개수만큼 감소시킵니다. 만약 이번에 배달 가능한 개수가 배달할 택배 개수보다 작다면, 배달할 택배 개수를 이번에 배달 가능한 개수만큼 감소시킨 뒤 다시 배달 스택에 담습니다.

수거 스택에서도 이번에 수거 가능한 개수를 cap으로 시작하여 배달 스택과 같은 방법으로 처리하면 됩니다.

각 집에서 배달 및 수거할 택배 상자의 최대 개수와, 트럭에 실을 수 있는 택배 상자의 최대 개수(cap)는 모두 50 이하입니다. 이를 상수 취급했을 때, 위 알고리즘의 시간복잡도는 O(n) 입니다. (n = 배달 및 수거할 집의 개수)

다른 방법 그리디 전략을 쓰지만 스택을 사용하지 않는 풀이 방법도 있습니다. 가장 먼 집부터 배달 상자 수와 수거 상자 수를 각각 누적 합을 구한 후, 둘 중에 하나가 cap을 넘는다면 누적한 배달 상자 수와 수거 상자 수를 각각 cap만큼 비우면서 이동한 거리를 answer에 더하는 방법입니다. 여기서 이동한 거리를 구하기 위해 상자가 비워질 때의 위치를 저장해 둡니다. cap만큼 비우면서 누적 배달 상자 수 또는 수거 상자 수가 음수가 될 수 있습니다. 누적 상자 수가 cap만큼 덜 채워졌을 경우로, 다음 집의 상자를 미리 배달하거나 수거하는 효과를 가져서 음수가 되어도 괜찮습니다.

def solution(cap, n, deliveries, pickups):
    answer = 0
    deliveries = deliveries[::-1]
    pickups = pickups[::-1]

    have_deli = 0
    have_pick = 0

    for i in range(n):
        have_deli += deliveries[i]
        have_pick += pickups[i]

        # 연산 결과가 음수라면 한 번에 실어 나갈 수 있는 용량 보다 적은 것
        while have_deli > 0 or have_pick > 0:
            have_deli -= cap
            have_pick -= cap
            answer += (n-i) * 2

    return answer

[robert-min]

이모티콘 할인 행사 (완전탐색)

discounts = [10, 20, 30, 40]
answer = [-1, -1]

def solution(users, emoticons):
    n, m = len(users), len(emoticons)
    discount_list = [0]*m

    def search(idx):
        global answer
        if idx == m :
            sale_num, cost_num = 0, 0
            # 모든 인원 학인
            for i in range(n) :
                tmp = 0
                for j in range(m) :
                    if users[i][0] <= discount_list[j] :
                        tmp += emoticons[j] * ( 100 - discount_list[j] ) // 100
                if tmp >= users[i][1] :
                    sale_num += 1
                else :
                    cost_num += tmp

            if sale_num > answer[0] or sale_num == answer[0] and cost_num > answer[1] :
                answer = [sale_num, cost_num]
            return

        # 할인율을 선택하는 모든 경우 확인
        for i in range(4) :
            discount_list[idx] = discounts[i]
            search(idx+1)

    search(0)

    return answer

[robert-min]

포화이진트리

참고

def division_search(left, right, arr):
    global flag
    if left == right:
        return arr[left]

    mid = (left + right) // 2
    if arr[mid] == '0':
        for i in range(left, mid):
            if arr[i] == '1':
                flag = False
                return
        for i in range(mid+1, right + 1):
            if arr[i] == "1":
                flag = False
                return
    division_search(left, mid - 1, arr)
    division_search(mid+1, right, arr)

def solution(numbers):
    global flag
    answer = []
    for n in numbers:
        flag = True
        # 이진수 변환
        n = bin(n)[2:]
        # print(n)

        # 해당 이진수를 표현할 포화이진트리 개수 확인
        index = 1
        node_count = 0
        while True:
            # 포화이진트리 노드 개수는 2^n - 1
            if pow(2, index) - 1 >= len(n):
                node_count = pow(2, index) - 1
                break
            index += 1
        # print(node_count)

        n = list(('0' * (node_count - len(n))) + n)
        division_search(0, len(n) - 1, n)

        if flag:
            answer.append(1)
        else:
            answer.append(0)

    return answer