[코드트리 파이썬] 정수 두 개의 합2

문제

 

---

풀이

투 포인터를 이용하면 된다.

n, k = map(int, input().split())

arr = []
for i in range(n):
    arr.append(int(input()))

arr.sort()

두 개의 합이 k이하가 되어야 하기 때문에 입력받은 배열을 정렬해준다.

res = 0
valSum = 0
j = n - 1

for i in range(n):
    while j != 0 and arr[i] + arr[j] > k:
        j -= 1

    if j <= i:
        break
    
    res += j - i

이 후 투포인터로 문제를 해결한다.

i와 j로 순회하며

j 위치와 i위치의 원소 합이 k이하일 때 까지 순회한다.

이 때 i는 오른쪽으로 j는 왼쪽으로 진행한다

반복을 종료한 후의 i와 j는 합이 k 이상인 상태이기 때문에

j값에서 i값을 빼주면 된다.

 

만약 j와 i가 교차되었다면 진행이 의미가 없으므로 반복을 탈출한다.

 

코드

n, k = map(int, input().split())

arr = []
for i in range(n):
    arr.append(int(input()))

arr.sort()

res = 0
valSum = 0
j = n - 1

for i in range(n):
    while j != 0 and arr[i] + arr[j] > k:
        j -= 1

    if j <= i:
        break
    
    res += j - i

print(res)