숫자로 이루어진 배열과 하나의 숫자 k가 주어졌을 때, 이 배열을 모든 쌍의 합이 정확히 k가 되도록 나눌 수 있는지 확인해야 하는 문제입니다.
예를 들어 입력이 arr = [1, 2, 3, 4, 5, 6], k = 7이라면, (2, 5), (1, 6), (3, 4)처럼 각 쌍의 합이 7이 되는 짝을 만들 수 있으므로 결과는 True입니다.
문제 해결 접근 방식
배열이 이미 오름차순으로 정렬되어 있다는 점을 활용하면, 투 포인터(Two Pointer) 기법으로 효율적으로 해결할 수 있습니다. 가장 작은 값과 가장 큰 값을 차례대로 짝지으면 되기 때문입니다.
알고리즘 단계
- 배열의 길이를 n이라고 합니다.
- n이 홀수라면 쌍으로 나누는 것이 불가능하므로 False를 반환합니다.
- low는 0(첫 번째 인덱스), high는 n-1(마지막 인덱스)로 초기화합니다.
- low < high인 동안 다음을 반복합니다.
- arr[low] + arr[high]의 합이 k와 같지 않으면 False를 반환합니다.
- low는 1 증가시키고, high는 1 감소시켜 안쪽으로 포인터를 이동합니다.
- 모든 쌍이 조건을 만족하면 True를 반환합니다.
구현 예제
def solve(arr, k):
n = len(arr)
# 요소 개수가 홀수면 쌍으로 나눌 수 없음
if n % 2 == 1:
return False
low = 0
high = n - 1
while low < high:
# 양 끝값의 합이 k가 아니면 실패
if arr[low] + arr[high] != k:
return False
low = low + 1
high = high - 1
return True
arr = [1, 2, 3, 4, 5, 6]
k = 7
print(solve(arr, k))입력
[1, 2, 3, 4, 5, 6], 7
출력
True
동작 원리 설명
정렬된 배열 [1, 2, 3, 4, 5, 6]에서 첫 번째 검사는 1 + 6 = 7로 조건을 만족합니다. 다음으로 포인터가 안쪽으로 이동하여 2 + 5 = 7, 마지막으로 3 + 4 = 7 역시 조건을 충족합니다. 모든 쌍이 성공했기 때문에 최종적으로 True가 반환됩니다.
만약 중간에 한 쌍이라도 합이 k와 일치하지 않으면 즉시 False를 반환하고 종료하므로, 불필요한 연산을 줄일 수 있습니다.
시간 복잡도 분석
- 시간 복잡도: O(n) — 두 포인터가 서로 만날 때까지 배열을 한 번만 순회합니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 두 개의 포인터 변수만 사용합니다.
이 방식은 정렬된 배열에만 적용 가능하다는 점에 유의하세요. 정렬되지 않은 배열이라면 먼저 O(n log n)의 정렬 과정을 거치거나, 해시 맵(딕셔너리)을 활용한 O(n) 접근 방식을 고려해야 합니다.