조회구조 개선으로 합 구하기, 투 포인터

1. 기본 개념 - 브루트포스로 풀기

def solution():
    ins = input()
    target = int(input())
    num = list(map(int, ins.split()))

    for repeat in range(len(num)):
        for i in range(repeat + 1, len(num)):
            if num[repeat] + num[i] == target:
                return [num[repeat], num[i]]

print(solution())

각각 리스트, 타켓을 입력받아서 변수에 넣어준다. num을 입력받아 띄어쓰기로 나눠주고, 반복문 안에서 반복문을 이중 실행시켜준다. repeat는 len(num) 만큼 반복시켜주고 num[repeat] 에 계속 반복적으로 num[0] , num[1] 을 더해줌으로써 타켓을 찾을 수 있다.

타켓을 찾는 순간 바로 그 값 두개를 리턴한다. 하지만 타겟을 찾기위해 브루트포스 풀이를 할 경우 평균 5,824밀리초라는 상당히 긴 시간이 나온다. 시간복잡도가 O(n^2) 이기 때문이다. 수가 수천개, 수만개로 많아지고 수의 크기가 수억, 수조 단위로 커지게 되면 하나씩 대입하여 푸는 풀이방식은 비효율적이다.

2. 첫번째 수를 뺀 결과 키 조회하기

3. 조회 구조 개선하기

4. 투 포인터에 대해

투포인터란 왼쪽 포인터와 오른쪽 포인터의 합이 타켓보다 크다면 오른쪽 포인터를 왼쪽으로, 합이 작다면 왼쪽 포인터를 오른쪽으로 옮기면서 값을 조정하는 방식이다. 타켓은 8이고 [1, 2, 3, 4, 5]가 있으면 시작을 [2, 3]에서 하여 [2, 4]로 옮겨가며 키워가는 방식이다. [2, 4] 로 옮기면 사이 합은 10이다. 만약 칸을 이동했는데 범위 내 수가 타켓보다 커졌다면 [3, 4]로 옮겨 범위 내 수의 합을 7로 줄일 수 있다. 이는 수를 모두 정렬한 상태에서만 사용할 수 있다.

브루트포스 방식으로 하나하나 다 대입하는 것보다 훨씬 더 빠른 결과를 얻을 수 있다.