문제 설명
세 개의 배열 A, B, C와 목표값 "sum"이 주어졌을 때, 각각 서로 다른 배열에서 가져온 세 요소 a, b, c가 존재하여 a + b + c = sum을 만족하는지 확인해야 합니다.
예를 들어, 입력이 다음과 같다고 가정해 보겠습니다.
- A = [2, 3, 4, 5, 6]
- B = [3, 4, 7, 2, 3]
- C = [4, 3, 5, 6, 7]
- sum = 12
이 경우 출력은 True가 됩니다. 왜냐하면 4 + 2 + 6 = 12를 만족하며, 4는 배열 A에서, 2는 배열 B에서, 6은 배열 C에서 각각 가져올 수 있기 때문입니다.
해결 방법
가장 직관적인 방법은 브루트 포스(Brute Force) 접근법입니다. 세 배열의 모든 조합을 하나씩 확인하면서 합이 목표값과 일치하는지 검사합니다.
알고리즘의 단계는 다음과 같습니다.
- 배열 A의 모든 요소에 대해 반복합니다.
- 배열 B의 모든 요소에 대해 반복합니다.
- 배열 C의 모든 요소에 대해 반복합니다.
- A[i] + B[j] + C[k]의 값이 sum과 같으면 True를 반환합니다.
- 모든 조합을 확인한 후에도 일치하는 값이 없으면 False를 반환합니다.
구현 예제
다음 코드를 통해 더 잘 이해할 수 있습니다.
def is_sum_from_three_arr(A, B, C, total):
for i in range(0, len(A)):
for j in range(0, len(B)):
for k in range(0, len(C)):
if (A[i] + B[j] + C[k] == total):
return True
return False
A = [2, 3, 4, 5, 6]
B = [3, 4, 7, 2, 3]
C = [4, 3, 5, 6, 7]
total = 12
print(is_sum_from_three_arr(A, B, C, total))입력
[2,3,4,5,6], [3,4,7,2,3], [4,3,5,6,7], 12
출력
True
시간 복잡도 분석
위 알고리즘은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n³)입니다. 여기서 n은 각 배열의 크기를 의미합니다. 따라서 배열의 크기가 커질수록 실행 시간이 급격히 증가할 수 있습니다.
성능을 개선하고 싶다면 해시 셋(Set)을 활용하여 두 배열의 합과 세 번째 배열의 요소를 매칭하는 방식으로 O(n²)까지 최적화할 수 있습니다. 하지만 작은 크기의 배열에서는 위의 단순한 브루트 포스 방식도 충분히 효율적이며, 이해하기 쉽다는 장점이 있습니다.