740. Delete and Earn

740. Delete and Earn

 

코드 설명

1. 문제 핵심 이해:
   • 특정 숫자를 선택하면 해당 숫자 * 빈도수를 점수로 얻습니다.
   • 그러나 선택한 숫자 (n)에 대해 (n−1)과 (n+1)은 선택할 수 없습니다.
2. 해결 전략:
   • 정렬 및 DP를 사용하여 숫자를 순차적으로 탐색.
   • earn1과 earn2를 사용하여 이전 상태를 추적.
     • earn1: 두 칸 이전의 최대 점수.
     • earn2: 한 칸 이전의 최대 점수.
3. 동작 원리:
   • 현재 숫자와 이전 숫자가 연속되지 않는 경우:
     • earn2 = earn2+curEarn  (현재 점수를 그대로 추가).
   • 현재 숫자와 이전 숫자가 연속된 경우:
     • earn2=max⁡(earn1+curEarn, earn2)
     • (현재 숫자를 포함한 점수와 포함하지 않은 점수 중 최대값 선택).
4. 최종 반환:
   • 모든 숫자를 탐색한 후 얻을 수 있는 최대 점수 earn2 반환.

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
    	"""
        # House Robber 랑 유사한 문제라고 함
        # 해쉬맵 Count {숫자: 개수} n숫자 x 개수만큼 벌수 있고, 
        # 숫자 n을 벌면 숫자 (n+1) 와 숫자 (n-1)는 모두 삭제 해야 함
        # DP+캐슁 사용
        """
        # 주어진 문제는 특정 숫자를 선택하여 점수를 얻는 동시에,
        # 해당 숫자 +1 및 -1은 사용할 수 없게 만드는 조건을 가짐.
        # House Robber 문제와 유사한 방식으로 DP를 활용하여 해결 가능.

        # 숫자의 개수를 카운트할 딕셔너리 초기화
        # count = Counter(nums)
        count = defaultdict(int)
        for n in nums:
            count[n] += 1  # 각 숫자의 빈도수를 카운트

        # 중복된 숫자를 제거하고 정렬된 리스트로 변환
        nums = sorted(list(set(nums)))

        # DP를 위한 두 변수 초기화
        earn1, earn2 = 0, 0  # earn1: 이전 이전까지의 최대 점수, earn2: 바로 이전까지의 최대 점수

        # 정렬된 숫자 리스트를 순회하며 최대 점수 계산
        for i in range(len(nums)):
            # 현재 숫자로 얻을 수 있는 점수
            curEarn = nums[i] * count[nums[i]]  # 현재 숫자 × 해당 숫자의 빈도수

            # 현재 숫자(nums[i])가 이전 숫자(nums[i-1])와 연속되는 경우
            if i > 0 and nums[i] == nums[i-1] + 1:
                # 현재 숫자를 포함한 점수와 포함하지 않은 점수 중 최대값 선택
                temp = earn2
                earn2 = max(curEarn + earn1, earn2)
                earn1 = temp  # 이전 값을 갱신
            else:
                # 현재 숫자가 이전 숫자와 연속되지 않는 경우
                temp = earn2
                earn2 = curEarn + earn2  # 현재 점수를 더한 새로운 최대값
                earn1 = temp  # 이전 값을 갱신

        # 최대 점수를 반환
        return earn2

 

결론

이 코드는 문제를 House Robber 문제와 유사한 방식으로 해결합니다:

1. 숫자 리스트를 정렬하고 중복을 제거.
2. 현재 숫자가 이전 숫자와 연속되는지 여부를 기준으로 점수 계산.
3. DP를 사용하여 최대 점수를 계산. 😊