알고리즘 공부 16일차

오늘은 프로그래머스 이모티콘 할인행사 문제를 풀어보았다. 이 문제를 처음 봤을때 떠올린 아이디어는 각각의 이모티콘 별로 10%~40%까지 4가지 경우이므로 총 4^7의 경우를 생각할 수 있었다. 이는 약 16000 정도고 이용자의 최대는 100이므로 시간 복잡도도 충분해 보일 것 같았다. 그래서 나는 dfs문제라고 생각하고 접근하였다.

def dfs_emo(users,emoticons,sales,max_list):
    if len(emoticons)==len(sales):
        plus_sum=0;sale_sum=0
        for i,j in users
            q=0
            for k in range(len(sales)):
                if sales[k]>=i:
                    q+=emoticon[k]*(1-sales[k])
            if q>=j:
                plus_sum+=1
            else:
                sale_sum+=q
        if plus_sum>=max_list[0]:
            if sale_sum>=max_list[1]:
                max_list[0]=plus_sum
                max_list[1]=sale_sum
        sales=[]
    else:
        for i in range(1,5):
            sales.append(i*0.1)
            dfs_emo(users,emoticons,sales,max_list)  
            
def solution(users, emoticons):
    sales=[]
    max_list=[0,0]
    dfs_emo(users,emoticons,sales,max_list)
    return max_list

이런식으로 짜보았다. 그런데 지금 프로그래머스가 채점이 지연되는 상황이어서 아직 맞은지는 확인하지 못하였다. 그래서 주피터로 돌려보았는데 계속해서 오류가 발생했다. dfs를 작동하는 과정에서 무한 감옥에 갇힌 것처럼 보인다. 이 부분에 대해서는 조금 더 자고 오후에 다시 고쳐봐야겠다.

 

추가:

예상대로 dfs가 문제가 있었다. 전체적인 코드 방향은 맞았지만 sales 리스트를 다시 사용하지 않고 다른 리스트를 이용하면 좀 더 직관적으로 재귀함수를 돌릴 수 있을 것 같았다. 그리고 sales의 내용물들은 0~1사이의 수로 저장해두었기 때문에 users[0]의 값과 비교하려면 *100을 취해주어야 했다. 아래는 수정한 소스코드이다.

def dfs_emo(users,emoticons,sales,max_list):
    if len(emoticons)==len(sales):
        plus_sum=0;sale_sum=0
        for i,j in users:
            q=0
            for k in range(len(sales)):
                if sales[k]*100>=i:
                    q+=emoticons[k]*(1-sales[k])
            if q>=j:
                plus_sum+=1
            
            else:
                sale_sum+=q
        if plus_sum>max_list[0]:
            max_list[0]=plus_sum
            max_list[1]=sale_sum
        elif plus_sum==max_list[0]:
            if sale_sum>=max_list[1]:
                max_list[0]=plus_sum
                max_list[1]=sale_sum
        sales=[]
        return max_list
    
    for i in range(1,5):
        a=sales+[i*0.1]
        dfs_emo(users,emoticons,a,max_list)
def solution(users, emoticons):
    sales=[]
    max_list=[0,0]
    dfs_emo(users,emoticons,sales,max_list)
    return max_list

항상 수정할 때 나는 중간에 print구문을 끼워서 어떤식으로 출력되고 있는지를 확인하는 식으로 디버깅을 한다. 그렇게 하면 어디서 작동이 안되는지, 어떻게 작동이 되는지를 확인할 수 있어서 보기 편하기 때문이다. 한동안은 프로그래머스 레벨 2단계를 계속 풀어보자!