코테를 위한 기본 알고리즘: 배열 페어의 합 구하기

안녕하세요! 저는 유능한 개발자이자 알고리즘 블로그 운영자입니다. 오늘은 "배열 페어의 합 구하기"라는 문제를 다루어보려고 합니다. 이 문제는 주어진 배열에서 두 개의 숫자를 선택하여 합한 값 중 최소값의 합을 구하는 알고리즘입니다.

 

바로 아래 정보에서 공부해봅시다!

 

 

코테를 위한 기본 알고리즘 로고

문제 내용

주어진 배열 **nums**에서 두 개의 숫자를 선택하여 합한 값 중 최소값의 합을 구하는 문제입니다.

 

문제 이해하기

주어진 배열에서 페어를 만들어 합을 계산하는 방식을 이해해야 합니다. 이 문제에서는 주어진 배열을 오름차순으로 정렬한 뒤, 앞에서부터 두 개의 숫자를 선택하여 페어를 만들고, 이때 최소값을 합에 더하는 방식으로 문제를 해결합니다.

 

풀이 코드

pythonCopy code
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)
            if len(pair) == 2:
                sum += min(pair)
                pair = []

        return sum

풀이 방법

1. 주어진 배열 **nums**를 오름차순으로 정렬합니다.
2. 합을 계산할 변수 **sum**을 0으로 초기화하고, 페어를 담을 리스트 **pair**를 생성합니다.
3. **nums**를 순회하면서 각 숫자를 **pair**에 추가합니다.
4. **pair**에 숫자가 2개가 되면, 두 숫자 중 최소값을 **sum**에 더합니다.
5. **pair**를 초기화합니다.
6. 모든 숫자를 순회한 뒤, 최종적인 sum 값을 반환합니다.

이 풀이 방법은 주어진 배열을 정렬하고, 오름차순으로 페어를 만들어가며 최소값을 더하는 방식을 사용합니다. 이렇게 하면 최소값의 합을 구할 수 있습니다.

 

시간 복잡도

주어진 배열을 정렬하는 데 O(n log n)의 시간이 소요됩니다. 그리고 주어진 배열을 순회하여 페어를 만드는 과정에서 O(n)의 시간이 소요됩니다. 따라서 이 알고리즘의 전체 시간 복잡도는 O(n log n)입니다.

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음

 

 

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기