[프로그래머스] 파이썬 - 이모티콘 할인 행사

문제

제한 사항

 

 

풀이

# 각 이모티콘의 할인율에 대한 모든 경우의 수를 구하는 dfs
def dfs(temp, depth):
    global array
    percentage = [10,20,30,40]
    
    # 이모티콘의 개수 만큼 dfs가 돌았을 때
    if depth == len(temp):
        # 얕은 복사를 통해 새로운 temp 생성
        array.append(temp[:])
        return
    for p in percentage:
        temp[depth] += p
        dfs(temp, depth + 1)
        temp[depth] -= p

 

각 이모티콘들은 10, 20, 30, 40의 할인율 중 하나의 할인율을 가질 수 있다.

따라서 이 문제를 풀기 위해선 각 이모티콘의 할인율에 대한 모든 경우의 수를 구하는 dfs함수가 필요했다.

(이모티콘의 길이가 최대 7이었기 때문에, 완전탐색을 사용할 수 있었다)

파이썬의 product 모듈을 사용해서 구할 수도 있었으나, 나는 이번 문제에서 dfs를 사용해 모든 경우의 수를 구했다.

 

for i in range(len(array)):
    serviceUser = 0
    profit = 0

    for user in users:
    useMoney = 0
        per, handMoney = user

        for j in range(len(emoticons)):
            # per 이상 할인하는 이모티콘은 구매
            if array[i][j] >= per:
                useMoney += emoticons[j] * ((100-array[i][j])/100)

        if useMoney >= handMoney:
            # 이모티콘 구매 비용의 합이 handMoney 이상이 되면, 이모티콘 플러스 서비스 가입
            serviceUser += 1
        else:
            profit += useMoney

    if answer[0] < serviceUser:
        answer = [serviceUser, int(profit)]
    elif answer[0] == serviceUser:
        if answer[1] < profit:
            answer = [serviceUser, int(profit)]

 

그 후, 모든 경우의 수의 배열 array의 길이 만큼 for문을 돌며 유저들의 이모티콘 구매 여부를 탐색했다.

 

각 유저는 두 개의 조건에 따라 이모티콘을 구매한다.

1. 본인의 조건 할인율 per 이상 할인하는 이모티콘은 구매한다.

2. 만약 1의 조건에 따라 구매한 이모티콘들의 비용이 본인의 handMoney 이상이면 서비스에 가입한다.

 

위의 조건을 만족하는 service 가입 유저들의 수와, 이익 profit을 

answer와 비교하며, service 가입 유저들의 수가 많고 이익이 많은 array의 원소를 찾으면 답을 구할 수 있었다.

 

 

오늘 배운 것

 

dfs에서 array에 경우의 수 배열인 temp를 삽입할 때

temp 자체를 삽입하면 값이 제대로 저장되지 않았다.

 

temp를 그대로 삽입할 경우, array에 추가된 temp배열들이 모두 같은 참조를 가리키기 때문에

temp의 값이 변경될 때마다 array에 저장된 모든 값이 함께 변경되어 생기는 문제였다.

 

이를 해결하기 위해 나는 temp[:]를 통해 temp와 독립된 리스트를 생성하여 array에 append 해주었다.

temp[:] 와 같이 작성하면 얕은 복사가 발생한다.

얕은 복사는 리스트의 요소들만 복사하고 복사된 리스트는 원래 리스트와 독립적인 메모리를 갖게 된다.

1차원 배열에서는 각 요소가 리스트나 객체가 아닌 단순한 값(여기서는 정수)이기 때문에,

얕은 복사만으로도 새로운 배열이 완전히 독립적으로 저장된다.

따라서 1차원 배열에서는 굳이 깊은 복사까지 할 필요가 없다고 한다.

 

하지만 배열의 요소가 참조타입일 경우!!! 깊은 복사를 해야한다

 

그동안 파이썬에서 깊은 복사와 얕은 복사를 사용할 때 deepcopy모듈을 사용했는데.

temp[:] 와 같이 작성해도 얕은 복사를 할 수 있음을 알게되었다.

 

코드

# 각 이모티콘의 할인율에 대한 모든 경우의 수를 구하는 dfs
def dfs(temp, depth):
    global array
    percentage = [10,20,30,40]
    
    # 이모티콘의 개수 만큼 dfs가 돌았을 때
    if depth == len(temp):
        # 얕은 복사를 통해 새로운 temp 생성
        array.append(temp[:])
        return
    for p in percentage:
        temp[depth] += p
        dfs(temp, depth + 1)
        temp[depth] -= p

def solution(users, emoticons):
    answer = [0,0]  
    global array
    array = []
    
    dfs([0] * len(emoticons),0)
    
    for i in range(len(array)):
        serviceUser = 0
        profit = 0
        
        for user in users:
            useMoney = 0
            per, handMoney = user
            
            for j in range(len(emoticons)):
                # per 이상 할인하는 이모티콘은 구매
                if array[i][j] >= per:
                    useMoney += emoticons[j] * ((100-array[i][j])/100)

            if useMoney >= handMoney:
                # 이모티콘 구매 비용의 합이 handMoney 이상이 되면, 이모티콘 플러스 서비스 가입
                serviceUser += 1
            else:
                profit += useMoney
            
        if answer[0] < serviceUser:
            answer = [serviceUser, int(profit)]
        elif answer[0] == serviceUser:
            if answer[1] < profit:
                answer = [serviceUser, int(profit)]
    return answer

 

프로그래머스