스파르타 코딩클럽

내일배움캠프 AI 웹개발자양성과정 2회차

알고리즘 강의 3주차 숙제

1. 쓱 최대로 할인 적용하기

Q.
다음과 같이 숫자로 이루어진 배열이 두 개가 있다.
하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다.
쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다.
이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가?
단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다.

[30000, 2000, 1500000] # 상품의 가격
[20, 40]               # 쿠폰, 할인율의 단위는 % 입니다.

shop_prices = [30000, 2000, 1500000]
user_coupons = [20, 40]


def bubble_sort(array):
    while True:
        sort_bool = True
        for i in range(len(array)-1):
            if array[i] < array[i+1]:
                array[i], array[i+1] = array[i+1], array[i]
                sort_bool = False
        if sort_bool:
            break

    return array


def selection_sort(array):
    n = len(array)
    for i in range(n):
        max_index = i
        for j in range(i+1, n):
            if array[j] > array[max_index]:
                max_index = j
            array[i], array[max_index] = array[max_index], array[i]

    return array


def insertion_sort(array):
    new_array = [array[0]]
    n = len(array)
    for i in range(1, n):
        new_array.append(array[i])
        m = len(new_array)
        for j in range(m-1, 1, -1):
            if new_array[j] > new_array[j-1]:
                new_array[j], new_array[j-1] = new_array[j-1], new_array[j]
            else:
                break

    return array


def insertion_sort_2(array):
    for i in range(len(array)):
        for j in range(i):
            index = i - j - 1
            if array[index+1] > array[index]:
                array[index], array[index+1] = array[index+1], array[index]
            else:
                break
    return array


def get_max_discounted_price(prices, coupons):
    prices = insertion_sort_2(prices)
    coupons = insertion_sort_2(coupons)

    index = 0
    result = 0

    while True:
        if index >= len(prices):
            break
        if index >= len(coupons):
            for i in range(index, len(prices)):
                result += prices[i]
            break

        result += prices[index] * (1 - coupons[index] / 100)
        index += 1

    return result


print(get_max_discounted_price(shop_prices, user_coupons))  # 926000 이 나와야 합니다.

2. 멜론 베스트 앨범 뽑기

Q. 멜론에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 한다.
노래는 인덱스 구분하며, 노래를 수록하는 기준은 다음과 같다.

1. 속한 노래가 많이 재생된 장르를 먼저 수록한다. (단, 각 장르에 속한 노래의재생 수 총합은 모두 다르다.)
2. 장르 내에서 많이 재생된 노래를 먼저 수록한다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다.

노래의 장르를 나타내는 문자열 배열 genres와
노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때,
베스트 앨범에 들어갈 노래의 인덱스를 순서대로 반환하시오.

genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]

# genres = ["hiphop",  "pop", "classic", "pop", "hiphop"]
# plays = [2000, 600, 8000, 2500, 2000]


def compare_album(album_1, album_2):
    if album_1[0] < album_2[0]:
        return True
    elif album_1[0] > album_2[0]:
        return False

    if album_1[1] > album_2[1]:
        return True
    elif album_1[1] < album_2[1]:
        return False

    if album_1[2] < album_2[2]:
        return True
    return False


def compare_play(genre_1, genre_2):
    if genre_1[1] > genre_2[1]:
        return True
    return False


def compare_default(num_1, num_2):
    return num_1 > num_2


def merge_sort(array, func=compare_default):
    if len(array) <= 1:
        return array
    mid = len(array) // 2
    left_array = merge_sort(array[:mid], func=func)
    right_array = merge_sort(array[mid:], func=func)
    return merge(left_array, right_array, func=func)


def merge(array_1, array_2, func=compare_default):
    merge_array = []
    index_1 = 0
    index_2 = 0

    while True:
        if index_1 >= len(array_1):
            merge_array.extend(array_2[index_2:])
            break

        if index_2 >= len(array_2):
            merge_array.extend(array_1[index_1:])
            break

        if func(array_1[index_1], array_2[index_2]):
            merge_array.append(array_1[index_1])
            index_1 += 1
        else:
            merge_array.append(array_2[index_2])
            index_2 += 1

    return merge_array


def get_melon_best_album(genre_array, play_array):

    all_genres = list(set(genre_array))
    all_plays = dict()

    for genre in all_genres:
        all_plays[genre] = 0

    for i, genre in enumerate(genre_array):
        all_plays[genre] += play_array[i]

    all_plays = list(all_plays.items())
    all_plays = merge_sort(all_plays, compare_play)
    all_plays = [(i, k, v) for i, (k, v) in enumerate(all_plays)]

    all_plays_dict = dict()
    for play in all_plays:
        all_plays_dict[play[1]] = (play[0], play[2])

    album_store = []
    for i, genre in enumerate(genre_array):
        album = (all_plays_dict[genre][0], play_array[i], i)
        album_store.append(album)

    merge_array = merge_sort(album_store, compare_album)

    album_store = dict()
    for order in all_plays:
        album_store[order[0]] = list()

    for album in merge_array:
        album_store[album[0]].append((album[1], album[2]))

    result = []
    for i, play in enumerate(all_plays):
        if album_store[i] is not None:
            result.append(album_store[i][0][1])
        if len(album_store[i]) >= 2:
            result.append(album_store[i][1][1])

    return result



print(get_melon_best_album(genres, plays))  #  [4, 1, 3, 0]

Github

https://github.com/kimphysicsman/nbcamp-algorithm-220726