알고리즘 - Python / 백준 - 9024번 : 두 수의 합

9024번: 두 수의 합 (acmicpc.net)

9024번: 두 수의 합

 

---

풀이

• 음수와 양수가 섞여있는 배열이 있을 때 , 두 수를 더해서 어떤 수에 가장 가깝게 나오는 경우가 몇 가지 인지 출력하는 문제다.
• 만약 4를 만들어야 하는데 5가 가장 가까운 수라면 , 더해서 5가 되는 조합의 개수를 출력해야 한다.
• 모든 구간을 확인해야 하는데 기준점이 있으므로 투 포인터로 해결하였다.
• 먼저 배열을 오름차순으로 정렬한 후 , 구하고자 하는 값과 비교해 크면 뒤쪽을 한칸 당기고 , 작으면 앞쪽을 하나 밀었다.
• 그리고 두 수를 더한 값과 기준값이 얼마나 차이나는지 확인하고 , 이전에 찾았던 값들보다 작다면 정답을 1로 돌리고 그 차이를 저장한다.
• 저장한 차이와 정답 수를 두 포인터가 만날 때까지 업데이트 하면 최종적인 답을 구할 수 있다.

 

import sys
n = int(sys.stdin.readline())
for _ in range(n):
    k,m = map(int , sys.stdin.readline().split(" "))
    c = list(map(int , sys.stdin.readline().split(" ")))
    c.sort(); fp,ep = 0,len(c)-1
    ans = 0; check_ans = 10**9
    while True:
        if fp == ep:
            break
        if c[fp] + c[ep] > m:
            space = abs(m - (c[fp] + c[ep]))
            if space < check_ans:
                check_ans = space
                ans = 1
            elif space == check_ans:
                ans += 1
            ep -= 1
        elif c[fp] + c[ep] < m:
            space = abs(m - (c[fp] + c[ep]))
            if space < check_ans:
                check_ans = space
                ans = 1
            elif space == check_ans:
                ans += 1
            fp += 1
        else:
            if check_ans == 0:
                ans += 1
            else:
                check_ans = 0
                ans = 1
            fp += 1
    print(ans)

---