백준_python 3273번 두 수의 합 (정렬, 투 포인터)

<문제 링크>

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

 

 

 

<정답 코드>

 sol 1 ) 배열에 인덱스 저장하고 값 비교해 계산 

n = int(input())
arr = list(map(int, input().split()))
x = int(input())
 
arr2 = [0] * 2000000
for i in range(n):
    arr2[arr[i]] = i
 
cnt = 0
for i in range(n):
    if arr2[x - arr[i]] > i:
        cnt += 1
 
print(cnt)

 

입력을 arr에 받고, 각 원소를 인덱스로 하는 arr2 배열에 인덱스를 저장했다.

정답이었지만, 문제를 잘못 이해한 풀이고,

메모리 사용(불필요하게 큰 arr2 배열) 측면에서 비효율적인 코드

시간복잡도 : O(n)

 

 

 

sol 2 ) 정렬과 투 포인터를 이용한 풀이

n = int(input())
arr = list(map(int, input().split()))
x = int(input())
 
# 배열 정렬 후 포인터 양쪽 끝에 두 개 설정
arr.sort()
left, right = 0, n - 1
cnt = 0
 
while left < right:
    current_sum = arr[left] + arr[right]
    if current_sum == x:
        cnt += 1
        left += 1
        right -= 1
    elif current_sum < x:
        left += 1
    else:
        right -= 1
 
print(cnt)

 

두 개의 포인터(left, right)를 정렬한 배열 양 쪽 끝에 두고

합이 x와 일치할때까지 이동하며 해당하는 값을 찾는 코드

시간복잡도가 O(n log n)으로 1번 코드보다 약간 느리지만 훨씬 적은 메모리 공간 사용

1번 코드보다 깔끔한 풀이