배열 요소에서 세 수의 합이 특정 값인 조합 찾기

06 Nov 2023

javascript

배열에서 세 개의 숫자를 선택하여 합이 특정한 값을 가지는 모든 조합을 찾는 알고리즘을 구현해 보겠습니다. 이러한 문제는 주어진 배열에서 조합을 찾는 것이므로, 조합(Combination)을 생성하는 알고리즘을 활용할 것입니다.

알고리즘 설명

주어진 배열을 정렬합니다.
배열을 순회하면서 첫 번째 수를 선택합니다.
두 번째 수를 선택하기 위해 첫 번째 수의 다음 인덱스부터 배열을 순회합니다.
세 번째 수를 선택하기 위해 두 번째 수의 다음 인덱스부터 배열을 순회합니다.
선택된 세 개의 수의 합이 특정한 값과 일치하는지 확인합니다. 일치하는 경우 조합을 저장합니다.
위의 과정을 모든 가능한 조합에 대해 수행합니다.

코드 예시 (Python)

def find_combination(nums, target):
    nums.sort()  # 배열 정렬
    combinations = []  # 조합 저장 리스트

    # 첫 번째 수 선택
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # 중복된 수 건너뛰기

        # 두 번째 수 선택
        left = i + 1
        right = len(nums) - 1
        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]
            if curr_sum == target:
                combinations.append([nums[i], nums[left], nums[right]])
                # 중복된 수 건너뛰기
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif curr_sum < target:
                left += 1
            else:
                right -= 1

    return combinations

# 테스트
nums = [2, 7, 4, 0, 9, 3, 5]
target = 11
result = find_combination(nums, target)
print(result)  # [[0, 2, 9], [2, 4, 5], [3, 4, 4]]

정리

위의 코드는 세 개의 수를 선택하여 합이 특정한 값과 일치하는 조합을 찾는 알고리즘입니다. 이 문제는 조합을 생성하는 알고리즘을 활용하여 해결할 수 있습니다. 주어진 배열을 정렬하고 첫 번째 수부터 순차적으로 선택하며, 나머지 두 개의 수는 포인터를 이동시키며 조합을 생성합니다. 합이 일치하는 경우 조합을 저장하고 중복된 수를 건너뛰는 작업을 수행합니다. 이를 모든 가능한 조합에 대해 반복하여 원하는 결과를 얻을 수 있습니다.

알고리즘 설명

코드 예시 (Python)

정리

참고 자료