고유한(unique) 요소들로 구성된 행렬과 하나의 목표 합계가 주어졌을 때, 두 요소가 반드시 서로 다른 행에서 선택되도록 하여 그 합이 주어진 값과 같아지는 모든 쌍(pair)을 찾는 문제입니다.
예를 들어 입력이 다음과 같다고 가정해 보겠습니다.
| 2 | 4 | 3 | 5 |
| 6 | 9 | 8 | 7 |
| 10 | 11 | 14 | 12 |
| 13 | 1 | 15 | 16 |
목표 합계(sum)가 13이라면 출력은 다음과 같습니다.
[(2, 11), (4, 9), (3, 10), (5, 8), (12, 1)]
문제 해결 접근 방식
이 문제는 각 행을 먼저 정렬한 뒤, 서로 다른 두 행을 하나씩 짝지어 투 포인터(two pointer) 기법으로 탐색하는 방식으로 효율적으로 해결할 수 있습니다. 구체적인 단계는 다음과 같습니다.
- 결과를 저장할 새 리스트
res를 생성하고, 행렬의 크기를n으로 설정합니다. - 모든 행을 오름차순으로 정렬합니다.
i를 0부터 n-2까지 순회하고, 각i에 대해j를 i+1부터 n-1까지 순회하며 서로 다른 두 행의 모든 조합을 선택합니다.- 선택된 두 행에 대해
low는 첫 번째 행(i번째)의 시작 인덱스 0으로,high는 두 번째 행(j번째)의 마지막 인덱스 n-1로 초기화합니다. low < n이고high >= 0인 동안 아래 과정을 반복합니다.matrix[i][low] + matrix[j][high]가 목표 합과 같으면 해당 쌍을res에 추가하고,low는 1 증가,high는 1 감소시킵니다.- 합이 목표 값보다 작으면
low를 1 증가시켜 더 큰 값을 탐색합니다. - 합이 목표 값보다 크면
high를 1 감소시켜 더 작은 값을 탐색합니다.
- 모든 탐색이 완료되면
res를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다. 참고로 내장 함수 sum()과의 충돌을 피하기 위해 매개변수 이름을 target으로 사용했습니다. 또한 이 구현은 행렬이 n×n 정방행렬이라고 가정합니다.
MAX = 100
def sum_pair(matrix, target):
res = []
n = len(matrix)
# 각 행을 오름차순으로 정렬
for i in range(n):
matrix[i].sort()
# 서로 다른 두 행의 모든 조합에 대해 투 포인터 탐색
for i in range(n - 1):
for j in range(i + 1, n):
low = 0 # i번째 행의 시작 포인터
high = n - 1 # j번째 행의 끝 포인터
while low < n and high >= 0:
current = matrix[i][low] + matrix[j][high]
if current == target:
res.append((matrix[i][low], matrix[j][high]))
low += 1
high -= 1
elif current < target:
low += 1
else:
high -= 1
return res
target = 13
matrix = [
[2, 4, 3, 5],
[6, 9, 8, 7],
[10, 11, 14, 12],
[13, 1, 15, 16]
]
print(sum_pair(matrix, target))
입력
[[2, 4, 3, 5], [6, 9, 8, 7], [10, 11, 14, 12], [13, 1, 15, 16]] target = 13
출력
[(4, 9), (5, 8), (2, 11), (3, 10), (12, 1)]
시간 복잡도 분석
각 행의 정렬에는 O(n log n)의 시간이 걸리고, n개의 행을 정렬하므로 정렬 단계의 총 비용은 O(n² log n)입니다. 이후 서로 다른 두 행의 조합은 최대 O(n²)개이며, 각 조합에 대한 투 포인터 탐색이 O(n)이므로 전체 시간 복잡도는 O(n³)입니다. 별도의 보조 자료구조를 사용하지 않으므로 결과 리스트를 제외한 추가 공간 복잡도는 O(1)입니다.