두 수의 합 백준 3273번 배열

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

문제 n개의 서로 다른 양의 정수 a1, a2, …, an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

해당 문제는 보통 투포인터로 풀게 되는데 나는 배열을 그대로 사용해서 어떻게 풀 수 없을까 하고 몇가지 고민을 해보았다.

num = int(input())
num_list = list(map(int,input().split()))
target = int(input())

일단 이렇게 입력을 받고

두가지 방법을 떠올렸는데 첫번째는 다른 배열을 하나 더 만들어서 인덱스로 문제를 풀려고 했다.

테스트 케이스에서 다음과 같이 있다고 가정을 하자

number_list: 5 12 7 10 9 1 2 3 11
target: 13

그리고 빈 리스트를 하나 만드는데 5를 넣게 되면 타겟 넘버인 13에서 5를 빼고 8이 존재하는지 확인을 한다. 아직 여기 빈 리스트에는 아무것도 존재하지 않으니 인덱스 5번의 값을 1로 바꾸고 넘어간다. 12의 경우에도 아직은 1이 들어오지 않았으니 넘어간다.

그렇게 쭉 진행하다가 1을 만나게 되었을때 인덱스 12가 1이 있으니 쌍을 이룰 수 있으니 카운트를 해줍시다.

문제는 인덱스를 확인할 배열의 길이를 어떻게 정할지 조금 고민이 있었다. 몇가지 시도를 해봤는데 인덱스 길이 조절을 못해서 인덱스 초과로 런타임 에러가 나왔는데

max_num = (max(num_list)+target)*2
    
check_list = [0]*max_num
count = 0
for idx, number in enumerate(num_list):
    if check_list[target-number]==1:
        count+=1
    check_list[number]=1
    
print(count)

인덱스 길이를 들어온 숫자의 최대값 + target 에다가 2를 곱한 값을 던져주니 대충 맞았다고 나왔다. 투포인터를 안쓰고 문제를 풀 수는 있었다.

만약 투포인터로 푼다고 하면 정렬을 쭉한다. 그러면 앞에서는 제일 작은 값 맨 뒤에는 가장 큰 값이 들어오게 되는데

이제 포인터를 양쪽 끝에 두고 포인터를 옮기기 시작한다.

두 포인터가 가르키는 값을 더했을때 타겟보다 작다면 왼쪽에 있는 포인터를 올리고 반대라면 오른쪽에 있는 포인터를 내려 가는 식으로 찾다가 뭐 아무튼 그러면 될거 같다.

count = 0
for idx,number in enumerate(num_list):
    check = (target - number)
    if check in num_list:
        count += 1
        num_list.remove(check)
print(count)

또 다른 방법으로 파이썬에는 (숫자 in 배열)로 찾을 수 있어서 배열 없이 바로 할 수 있을까 했지만

생각보다 이게 비효율이다. 배열속에 해당 숫자를 찾는 과정이 O(1)이 아니라 O(n)이기 때문에 사실상 O(n^2)의 형태로 코드가 돌아가기 때문이다.