[hackerrank] Luck Balance (Python)

레나는 인생은 새옹지마가 좌우명인 듯 하다.

문제 (링크)

• 레나는 코딩 대회를 나가기 전에 여러 번의 사전 콘테스트에 참가한다
• 그녀의 운은 0으로 시작해서, 사전 콘테스트를 치를 때마다 운을 적립한다고 믿는다
• 두 개의 어레이는 각각 amount of luck 과 콘테스트의 중요도를 가리킨다
• 사전 콘테스트에 지면 운은 증가하고, 이기면 운이 감소한다
• 콘테스트의 중요도는 1이면 중요함, 0이면 중요하지 않음으로 구분한다
• 주어진 숫자 k는 '중요한 콘테스트'를 질 수 있는 최대 횟수이다

풀이

def luckBalance_1(k, contests):
    # Write your code here
    answer=0
    candi = [] # 중요한 콘테스트만 담을 리스트
    for i in contests:
        if i[1] ==0:
            answer+=i[0] # 중요하지 않은 콘테스트는 모두 져도 된다
        else:
            candi.append(i)
            
    candi.sort(reverse=True)
    
    for a,b in enumerate(candi): # 중요한 콘테스트는 k번만 질 수 있다
        if a+1 <=k:
            answer+=b[0]
        else:
            answer-=b[0]
            
    return answer
    
# 10000 iteration 0.251 seconds

 그리디 알고리즘 문제. 디스커션에는 애초에 amount of luck을 기준으로 정렬하고 중요한 콘테스트를 k번만 지게 만드는 코드가 더 짧았지만, 전체 리스트를 정렬하는 것보다 중요한 콘테스트만 뽑아서 정렬하는 것이 더 낫다고 생각했다. 주말이니까 굳이 test case중에 긴 것들을 가져와서 10000번 반복해서 시간 비교를 해보고 주석에 추가해두었다...ㅎ 생각과는 다르게 짧은 코드가 더 빨랐지만 엄청난 차이는 나지 않았다. (마지막 자존심)

---

 

# copied from discussion
def luckBalance_2(k, contests):
    total_luck = 0
    for luck,important in sorted(contests, reverse=True):
        if not important:
            total_luck += luck
        elif k:
            total_luck += luck
            k -= 1
        else:
            total_luck -= luck
    return total_luck
    
# 10000 iteration 0.181 seconds