2022.04.09 [백준] (파이썬 python) 두 수의 합

 

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

3273번: 두 수의 합

 

---

풀이

처음 이 문제를 단순히 for문을 돌려 모든 상황을 고려해 풀이 했지만 시간초과가 발생했다.

그래서 두 포인터를 사용하여 코드를 작성하였다.

우선 배열을 정렬한 후, left, right를 0, n-1로 설정해 주었다. 

이 후, while문을 돌려 arr[left] + arr[right]를 temp에 저장 후, x와 같으면 cnt를 1 증가시키고 left를+1증가 시키고 다음 while문으로 넘어간다. 만약 temp가 x보다 작으면 left를 1증가시켜준다. 이유는 x보다 작으면 left를 증가시켜 주어야 최소값을 증가시키기 때문이다. 그리고 x보다 크면 right값을 1감소 시킨다. 

그리고 left와 right가 같아지면 while문을 종료한다.

n=int(input())
arr=list(map(int,input().split()))
x=int(input())
cnt=0
arr.sort()
left=0
right=n-1
while left<right:
    temp=arr[left]+arr[right]
    if temp == x:
        cnt+=1
        left+=1
    elif temp < x:
        left+=1
    else:
        right-=1
print(cnt)