이 글에서는 주어진 숫자 목록에서 두 수의 차이가 정확히 k와 같은 쌍(pair)의 개수를 세는 방법을 살펴봅니다. 숫자들은 리스트 형태로 제공되며, 프로그램 실행 시 원하는 차이 값 k를 함께 전달합니다.
방법 1: for 루프 사용하기
가장 직관적인 방법은 서로 중첩된 두 개의 for 루프를 사용하는 것입니다. 바깥쪽 루프는 리스트의 각 요소를 하나씩 방문하는 역할을 하고, 안쪽 루프는 현재 요소와 나머지 요소들을 하나씩 비교합니다. 두 요소의 차이가 k와 일치하면 카운트 변수(count)의 값을 1씩 증가시킵니다.
예제 코드
listA = [5, 3, 7, 2, 9]
k = 2
count = 0
# 리스트의 각 요소를 방문
for i in range(0, len(listA)):
# 가능한 모든 쌍을 만들어 비교
for j in range(i + 1, len(listA)):
if listA[i] - listA[j] == k or listA[j] - listA[i] == k:
count += 1
print("Required Pairs: ", count)
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Required Pairs: 3
리스트 [5, 3, 7, 2, 9]에서 차이가 2인 쌍은 (5, 3), (5, 7), (7, 9)로 총 3개입니다.
방법 2: while 루프 사용하기
두 번째 방법은 while 루프와 if-else 조건문을 활용하는 투 포인터(two pointer) 기법입니다. 먼저 리스트를 오름차순으로 정렬한 뒤, 두 인덱스가 가리키는 값의 차이를 k와 비교하여 인덱스를 상황에 맞게 이동시킵니다. 차이가 k보다 크면 작은 쪽 값을 키우고(next_index 증가), 차이가 k보다 작으면 큰 쪽 값을 키워(current_index 증가) 차이가 정확히 k가 되는 지점을 찾아냅니다.
예제 코드
listA = [5, 3, 7, 2, 9]
k = 2
count = 0
# 투 포인터 기법 적용을 위해 리스트 정렬
listA.sort()
next_index = 0
current_index = 0
while current_index < len(listA):
if listA[current_index] - listA[next_index] == k:
count += 1
next_index += 1
current_index += 1
elif listA[current_index] - listA[next_index] > k:
next_index += 1
else:
current_index += 1
print("Required Pairs: ", count)
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
Required Pairs: 3
두 방법의 성능 비교
중첩 for 루프 방식은 가능한 모든 쌍을 검사하므로 시간 복잡도가 O(n²)입니다. 반면 while 루프 방식은 정렬에 O(n log n), 탐색에 O(n)이 소요되어 전체적으로 O(n log n)으로 더 효율적입니다. 따라서 데이터의 크기가 커질수록 정렬 후 투 포인터를 활용하는 방식이 유리합니다.