[그리디] -카드 점수

카드 점수

N개의 카드가 일렬로 놓여져 있습니다. 각 카드에는 숫자가 적혀있습니다.
현수는 카드가 일렬로 놓여진 줄의 양 끝 즉 왼쪽 맨 끝카드와 오른쪽 맨 끝 카드 둘 중 하나 를 가져갈 수 있습니다.

현수는 양 끝에서 가져가는 방식으로 k개의 카드를 가져갈 수 있습니 다.

그리고 가져간 카드에 적혀진 숫자의 총합이 현수가 얻는 점수입니다.
일려로 놓여진 각 카드의 숫자가 매개변수 nums에 주어지고,

현수가 가져갈 수 있는 카드의 개수 k가 주어지면 현수가 얻을 수 있는 최대점수를 반환하는 프로그램을 작성하세요.

제한사항:
• nums의 길이는 300,000을 넘지 않습니다.
• nums의 원소는 100을 넘지 않는 자연수입니다..

• 2 <= k < nums의 길이

입력예제 1번 설명 :
왼쪽에서 2, 3, 7, 오른쪽에서 5 이렇게 4개를 가져가면 최대가 됩니다. 2+3+7+5=17

 

나의 코드

 

def solution(nums, k):
    answer = 0
    Sl=len(nums)-k
    Minn=100
    p1=0
    p2=p1+Sl
    while p2!=len(nums)+1:
        if sum(nums[p1:p2])<Minn:
            Minn=sum(nums[p1:p2])
            print(p1,p2)
        p1+=1
        p2+=1

    answer=sum(nums)-Minn
    

    return answer
        
                                         
print(solution([2, 3, 7, 1, 2, 1, 5], 4))
print(solution([1, 2, 3, 5, 6, 7, 1, 3, 9], 5))
print(solution([1, 30, 3, 5, 6, 7], 3))
print(solution([1, 2, 15, 3, 6, 7, 8, 9], 5))
print(solution([12, 5, 6, 12, 34, 35, 13, 3, 7, 8, 9], 7))

슬라이드 를 사용해서 해결 하였다.

슬라이드의 시작고 끝을 p1,p2로 잡았는데 뭔가 더 깔끔하게 표현한느 법이 있을텐데..

라는 찜찜함으로 구현을 했고 결론적으로 뭐 문제없이 잘 푼거 같다.

 

 

정답 코드 1

def solution(nums, k):
    answer = 0
    n = len(nums)
    for i in range(k+1):
        sumN = 0
        for j in range(i):
            sumN += nums[j]
        for j in range(n-k+i, n):
            sumN += nums[j]
        answer = max(answer, sumN)
  
    return answer

 

정답 코드 2

def solution(nums, k):
    total = sum(nums)
    m = len(nums) - k
    score = 0
    for i in range(m):
        score += nums[i]
    minS = score
    left = 0
    for right in range(m, len(nums)):
        score += (nums[right] - nums[left])
        left += 1
        minS = min(minS, score)

    return total - minS
        
                                         
print(solution([2, 3, 7, 1, 2, 1, 5], 4))
print(solution([1, 2, 3, 5, 6, 7, 1, 3, 9], 5))
print(solution([1, 30, 3, 5, 6, 7], 3))
print(solution([1, 2, 15, 3, 6, 7, 8, 9], 5))
print(solution([12, 5, 6, 12, 34, 35, 13, 3, 7, 8, 9], 7))

 

정답 코도는 두개의 시간 복잡도로 나뉘어서 총 두개가 있다.

이중 반복문을 사용한 코드와 나와 같은 슬라이드를 활용한 코드이다.

슬라이드의 right를 반복문의 변수로 사용해서 '나'의 기준에서는 오히려 

나의 코드보다 가독성이 떨어진다 생각한다. 나의 코드가 나은듯 ㅋㅅㅋ