[백준] 3273번 두 수의 합 (투포인터 문제)

사용 언어 - Python3

문제 -  3273번 두 수의 합

투포인터 : 가능성을 지워주는 방법

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

 

3273번: 두 수의 합

 

정답

양쪽 끝에서 비교하면서 만나면 종료

arr[s] + arr[e]

 

완전탐색 방법) 첫번째 숫자랑 2~n번째 숫자 더해주기 + 두번째 숫자랑 3~n번째 숫자 더해주기....

=> 시간 복잡도 문제 !

 

투포인터 알고리즘 활용

arr 정렬 후, s = 0 시작지점 / e = n-1 끝지점

arr[s] + arr[e] 가 x라면, cnt += 1

x이상이라면, 마지막 커서를 한 칸 왼쪽으로 이동해준다.

아니라면, 왼쪽 커서를 한 칸 오른쪽으로 이동해준다.

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

s = 0
e = n-1

cnt = 0
while s < e: #만나면 멈춰라
    # 정답조건
    if arr[s] + arr[e] == x:
        cnt += 1
        
    if arr[s] + arr[e] >= x:
        e -= 1
    else:
        s += 1
        
print(cnt)

 

 

 

레퍼런스

• 깃허브 정답

https://github.com/yyeongeun/codingtest/blob/main/BAEKJOON/3273_%EB%91%90%EC%88%98%EC%9D%98%ED%95%A9.py