[LeetCode_561] 배열 파티션 I

파이썬으로 배우는 알고리즘 책을 공부하며 풀었던 LeetCode문제들을 재정리해보자.

 

# 문제 설명 

561번 Array Partition I은 n개의 페어를 이용한 min(a, b)의  합으로 만들 수 있는 가장 큰 수를 출력하는 문제이다.

Example

이 문제는 내가 지금까지 풀었던 문제들 중 가장 효율적으로 작성한 풀이이지 않나 싶다. 규칙을 찾아서 풀어서 효율적으로 나온거 같기도 하다..😀

책 풀이 확인해보니까 내가 푼 방법과 유사하여 따로 설명은 생략하겠다.

 

# 풀이방법 1 - 단순 list와 for문으로 판별 (내 풀이 - 효율적)

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        
        nums.sort()
        result = 0
        
        for _min in nums[::2] :
            result += _min    

        return result 
    
    '''
    규칙 : 
    - 내림차순 및 오름 차순 정렬 후 순서대로 2개씩 짝지어 min 값을 넣으면 됨 
    - 어떻게 보면 홀수번째의 합을 구하면 됨 
    '''

| 규칙 |
내림차순 및 오름차순 정렬 후 순서대로 2개씩 짝지어 min 값을 넣으면 됨 
어떻게 보면 홀수번째의 합을 구하면 됨

 

| 핵심 |

for _min in nums[::2] :

# [::2]는 2칸씩 뛰어 넘음(홀수번째 가능)

 

 

| 알고리즘 예시 적용 (규칙 설명) |

[6,2,6,5,1,2]
# 그냥 시도
6,5 ->5
6,2 ->2
1,2 -> 1
8

# !규칙 적용 시!
6,6 ->6
2,5 ->2
1,2 ->!
=>9


---------------
[1,2,3,4]
# 그냥 시도
1,4 ->1
2,3 -> 2

# !규칙 적용 시!
3,4 ->3
1,2 -> 1
=> 4

------------
[1,1,2,2,3,3,4,4]
# 그냥 시도
4,3->3
4,3 ->3
1,2 ->1
1,2 ->1
-> 8

# !규칙 적용 시!
4,4 ->4
3,3 ->3
2,2 ->2
1,1 -> 1
=>10

-----------------------------
[1,2,5,7,7,8,8,8]
# 그냥 시도
8,7 ->7
8,7 ->7
8,5 ->5
2,1->1
-> 20

# !규칙 적용 시!
8,8,->8
8,7->7
7,5->5
2,1 ->1
=>21
----------------
규칙 : 
내림차순 및 오름차순 정렬 후 순서대로 2개씩 짝지어 min 값을 넣으면 됨 
어떻게 보면 홀수번째의 합을 구하면 됨

 

 

 

 

 

# 결과 

😊✌