[코딩테스트 공부] 두 수의 합

출처 : https://www.acmicpc.net/problem/3273

문제부터 분석을 해보겠습니다

우선 N의 조건과 시간 제한 조건을 분석해보겠습니다.

N의 경우 100000까지로 제한이 되어있고, 시간 제한은 1초이므로 1억 회의 연산까지만 허용이 되어있는 상황입니다.

그러나 문제의 경우, 하나의 리스트에 대해서 1번의 순회와 1번의 탐색이 진행이 되어야하는 상황이기 때문에, O(NlogN)의 복잡도를 가지도록 문제 해결을 구상할 생각입니다.

따라서, O(logN)의 복잡도를 가지는 이진탐색 을 이용해서 문제 해결을 구성할 예정입니다.

문제 해결의 전략

제 문제 해결 전략은 매우 간단합니다.

리스트를 순회하면서, 순회중인 숫자에서 목표치를 빼준 값을 리스트에서 이진 탐색을 이용해서 찾아준다

이렇게 문제 해결을 구상하게 되면, 저희가 생각했던 O(NlogN)의 복잡도로 문제를 해결할 수 있음을 알 수 있습니다.

그러면, 이제 코드를 확인해볼까요?

코드를 확인하겠습니다

# 3273 두 수의 합

import sys

input = sys.stdin.readline

def binary_search(search_data, target_list, start, end):
    if start > end:
        return None
    
    mid = (start + end) // 2
    
    if target_list[mid] == search_data:
        return mid
    elif target_list[mid] > search_data:
        end = mid - 1
    else:
        start = mid + 1
        
    return binary_search(search_data, target_list, start, end)

N = int(input())

number_list = list(map(int, input().split()))
x = int(input())
count = 0

number_list = sorted(number_list)

for number in number_list:
    target_number = x - number
    
    if binary_search(target_number, number_list, 0, N - 1) != None:
        count += 1
        
print(count // 2)

코드를 보시게되면, 제가 위에서 말했듯이, 순회 중인 숫자에서 목표치를 빼준 값을 통해서 이진 탐색을 수행하는 모습을 확인 가능합니다.

그러나, 특이한 부분이 있습니다. 마지막에 count에 2를 나눈 몫을 출력해주는 모습을 확인이 가능한데요, 이유는 다음과 같습니다.

2개의 원소로 구성된 순서쌍은 서로 순서가 바뀌는 경우가 있기 때문에, 정확하게 2를 나눠주면 우리가 구하고자 하는 값이 구해진다

따라서, 위의 코드를 통해 문제는 해결되었습니다. 간단하죠?