[코딩인터뷰] 배열 - 배열 파티션 문제풀이

문제

n개의 페어를 이용한 min(a, b)의 합으로 만들 수 있는 가장 큰 수를 출력하라.

 

입력: [1, 4, 3, 2]
출력: 4

 

min(1, 2) + min(3, 4)일 경우에 최대값 4를 출력하게된다.

 

 

 

 

나의 코드

# min(a, b)의 합으로 만들 수 있는 가장 큰수
# 정렬
# 앞에서 2개씩 묶기
# 작은겄기리 묶고 큰것끼리 묶어야 최소값의 합이 가장 커진다
# [1, 4, 3, 2] -> [1, 2, 3, 4]
# 앞에서부터 2개씩 묶었을때 짝수번째의 원소만 추출하면 된다.

nums = [1, 4, 3, 2]

nums.sort()

result = 0

# 반복문 인덱스를 사용하여 짝수번째 원소만 추출
for i, a in enumerate(nums):
    if i % 2 == 0:
        result += a

print(result)

 

해당 문제의 의도를 파악하면 쉬운 문제다. 예시의 경우 리스트가 [1, 4, 3, 2]일 때를 보자. 결과적으로 최대값 추출이 목적이지만 함수는 min() 이기 때문에 최소값을 구하여 덧셈을 실행하게 된다. 이때 작은수끼리, 큰수끼리 묶여야 각 min(a, b)에서 최소값이 추출되더라도 충 합은 최대값이 될 수 있다. 그리고 또 알수있는 점은 리스트가 정렬된 경우이다. [1, 4, 3, 2]가 정렬된다면 [1, 2, 3, 4]가 된다. 따라소 오름차순으로 정렬된 리스트가 되기 때문에 여기서 짝수번째의 원소를 추출하면 그게 최소값이 된다. 2개씩 묶이기 때문에 정렬된 데이터에서는 왼쪽이 작은 값임을 알 수 있다.

 

 

 

 

정답코드

1) 2개씩 건너띄며 합하는 방식

from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        # 정렬 후 2개씩 건너띄며 합하기
        return sum(sorted(nums)[::2])

 

2) pair 리스트를 활용하는 방식

from typing import List


class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        sum = 0
        pair = []

        # 정렬
        nums.sort()

        for n in nums:
            # 앞에서 부터 오름차순으로 페어를 만들어 합 계산
            pair.append(n)

            # pair 리스트에 2개씩 쌓일때마다 실행한다는 의미
            if len(pair) == 2:
                sum += min(pair)
                pair = []  # 2개가 쌓였으면 다시 리셋하여 그 다음 2개 쌓일때를 기다림

        return sum

출처: github.com/onlybooks/algorithm-interview

 

 

 

 

 

문제풀이

1번의 정답코드 풀이

 

1) 설명

# 정렬 후 2개씩 건너띄며 합하기
return sum(sorted(nums)[::2])

 

위 '나의코드'에서 내가 짠 코드와 비슷하다. 리스트의 정렬을 실행하고 2개씩 건너띄며 원소를 찾는다. 따라서 0번째, 2번째 원소를 찾게되고 해당 번째의 원소를 찾은 이유는 내가 위에서 설명한 이유와 같다.

 

 

2번의 정답코드 풀이

 

1) 설명

pair = []

 

pair 라는 리스트 타입의 변수를 선언했다.

 

 

2) 설명

# 정렬
nums.sort()

 

정렬을 수행한다.

 

 

3) 설명

for n in nums:
    # 앞에서 부터 오름차순으로 페어를 만들어 합 계산
    pair.append(n)

    # pair 리스트에 2개씩 쌓일때마다 실행한다는 의미
    if len(pair) == 2:
        sum += min(pair)
        pair = []  # 2개가 쌓였으면 다시 리셋하여 그 다음 2개 쌓일때를 기다림

return sum

 

pair 리스트에 각 원소를 차례대로 담는다. 반복문이 실행될때마다 담으므로 정렬된 리스트에서는 최소값부터 담아지는 것을 확인할 수 있다. 그리고 그렇게 담아지면서 pair에 원소가 2개씩 쌓일때마다 최소값을 구해서 sum 변수에 담는다. 그리고 pair 리스트를 다시 비어주게 된다. 이렇게 되면 pair 리스트는 2개씩 쌓일때마다 min() 함수를 호출하게되고, 리스트가 비어지게된다.