3273번 두 수의 합

3273번: 두 수의 합

문제

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

입력

첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)

출력

문제의 조건을 만족하는 쌍의 개수를 출력한다.

# 3273번 두 수의 합
n = int(input())
nums = list(map(int,input().split())) 
target = int(input())
nums.sort()

s = 0
e = len(nums)-1

cnt = 0

#만약 x면 end -=1, start+=1
#만약 x보다 크면 end -=1
#만약 x보다 작으면 start=+1
while e>s:
    sum = nums[s]+nums[e]
    print(sum)
    if sum==target:
        cnt+=1
        print(cnt)
        e-=1
    elif sum>target:
        e -=1
    elif sum<target:
        s+=1
print(cnt)

느낀 점:

유튜브에서 10분짜리 강의 영상을 보고 처음 풀어 본 투포인터 문제.

영상에서 보여준 예시대로, Start,End 포인터가 한쪽 (왼쪽)에서 시작한다고 생각했으면 풀기 어려웠을 것 같다.

근데 문제 풀기전에 어떤 블로그에서 두 포인터가 양쪽에서 시작해서 점점 좁아지는 형태도 있다는 글을 보아서 바로 연상되어서 풀 수 있었다.

역시 머릿속에 소스를 많이 넣어놔야 문제 풀 때 아이디어를 쉽고 빠르게 떠올릴 수 있을 것 같다. 소마 코테전까지 문제를 많이 접해봐야지.

그리고, print로 디버깅하다보니 출력초과 오류가 잦다. 좀 덜 급하게 하자.