[BOJ] 3273. 두 수의 합

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

3273번: 두 수의 합

 

 

1. 해결방법

"""
1. 아이디어
- for문을 사용해서 ai의 값을 순차적으로 설정
- 이중 for문을 사용해서 ai를 제외한 원소를 aj로 순차적으로 선정
- ai + aj에서 나온 값을 x와 비교
- 비교한 값이 일치하다면 count
--> 위의 방식은 시간 초과 발생 새로운 아이디어 생각해야함
- 투포인터를 활용하면?
- 배열을 오름차순으로 정렬
- ai은 왼쪽부터 aj는 오른쪽부터 순차적으로 이동
- ai + aj가 x보다 클 경우, aj(오른쪽) 원소의 위치를 -1, 작다면 ai(왼쪽)의 원소를 +1
- 합이 x라면 count

 2. 시간복잡도
 - n = 10^6 -> O(n x n) -> 10^12 시간 초과
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline

n = int(input())
nums = sorted(list(map(int, input().split())))
x = int(input())

count = 0
left, right = 0, n - 1
add_num = 0

while nums[left] < nums[right]:
    add_num = nums[left] + nums[right]

    if add_num == x:
        count += 1
    if add_num < x:
        left += 1
    else:
        right -= 1

print(count)

원래라면 이중for문을 사용했을 것이다. 아니 처음에는 그렇게 생각하다가 시간복잡도를 계산해보니 파이썬 1초 연산 시간을 초과해버린 것이다.
그렇다면 투 포인터를 이용해서 단일 For문을 사용해야 한다.

로직 자체는 어렵지는 않으나 시간복잡도를 고려해서 빠르게 투포인터 라는것을 눈치채야 한다.