악곱 == 악성곱슬

구현, 투 포인터, 정렬

---

해당 문제는 두 수의 합이 x인 개수를 세는 문제이다. 완전 탐색, 즉 O(N^2)을 사용하여 풀 수 있는 문제이다. 그리고 입력의 크기를 보면 길이가 10만이므로 최대 O(NlogN)까지 사용할 수 있음을 파악한다. 따라서 투 포인터 알고리즘을 생각해낼 수 있다.

• 리스트를 정렬한다
• 처음과 끝을 잡고 두 포인터를 이동하며 합이 x인 것을 찾는다 → O(2N) = O(N)

시간 복잡도가 대폭 감소됨을 알 수 있다.

import sys

def solution(n, x):
    # 두 포인터 생성
    front, back = 0, n-1

    # 앞이 뒤를 넘어설 때 까지
    answer = 0
    while front < back:
        tmp = li[front] + li[back]
        # 두 합이 더 크면
        if tmp > x:
            back -= 1
        # 두 합이 같다면
        elif tmp == x:
            answer += 1
            front += 1
        # 두 합이 더 작으면
        else:
            front += 1
    print(answer)

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    li = list(map(int, sys.stdin.readline().rstrip().split()))
    X = int(sys.stdin.readline().rstrip())
    li.sort()
    solution(N, X)