문제 링크

문제 소개

해당 문제는 어떠한 수열에서 원소가 다른 원소 2개의 합인 것이 몇개 있는지 물어보는 문제이다.

해당 문제를 풀기 위해 아래의 코드와 같이 문제를 풀었다.

import sys


def check(arr, num):
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == num:
                return True
    return False


def solution():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    numbers = list(map(int, input().split()))
    numbers.sort(reverse=True)
    temp = []
    ans = 0
    while numbers:
        number = numbers.pop()
        if check(temp, number):
            ans += 1
        temp.append(number)
    print(ans)


solution()

위의 코드를 간략하게 정리하자면 주어진 수열을 정렬한 다음 다른 원소 2개의 합도 2차 반복문으로 풀었다. 그리고

하지만, 시간초과가 발생하였다. 그 이유는 우선 완전 탐색으로 O(n^3)이다. 그럼으로 이러한 과정을 줄이는 것이 필요하다.

투 포인터를 두어 아래의 조건을 성립하도록 한다.

두 포인터(왼쪽, 오른쪽) 세팅
1. 두 포인터에 해당하는 값들의 합이 찾으려는 수보다 작을 경우, 왼쪽 포인터를 +1함
2. 두 포인터에 해당하는 값들의 합이 찾으려는 수보다 클 경우, 오른쪽 포인터를 -1함

이러한 방식으로 찾아서 만약 값들의 합이 찾으려는 수와 같을 경우, 카운트해준다.

import sys


def solution():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    numbers = list(map(int, input().split()))
    numbers.sort()
    ans = 0
    for target in numbers:
        left, right = 0, N - 1
        while left < right:
            temp = numbers[left] + numbers[right]
            if temp == target:
                ans += 1
                break
            elif temp < target:
                left += 1
            else:
                right -= 1
    print(ans)


solution()

위의 코드처럼 풀었지만 틀렸다. 왜냐하면, 주어진 문제에서 Ai의 범위가 자연수가 아닌 정수이기 때문에 음수와 0도 생각해줘야 한다.

그럼으로 조건을 찾을 때 자기 자신을 제외시켜주지 않으면 0과 자기 자신의 수가 만났을 경우 카운트를 해주지 않아야 하지만 카운트 되는 불상사가 발생한다.

예를 들어, 아래와 같이 입력이 들어왔다.

4
0 1 2 4

그렇다면 정상적인 출력은 0이 될것이다. 왜냐하면 자기 자신을 더하지 않기 때문이다. 하지만 위의 틀린 코드 2에서는 3이 나온다. 왜냐하면 1을 기준으로 두 수를 찾을 때, 0과 자기 자신인 1을 찾기 때문에 최종적으로 3이 카운트된다.

이러한 경우를 개선하고자 슬라이싱을 통해 자기 자신을 제외하였다.

그럼으로, 최종 코드는 아래와 같다.

최종 코드

import sys


def solution():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    numbers = list(map(int, input().split()))
    numbers.sort()
    ans = 0
    for i in range(N):
        tmp = numbers[:i] + numbers[i+1:]
        left, right = 0, len(tmp) - 1
        while left < right:
            tempSum = tmp[left] + tmp[right]
            if tempSum == numbers[i]:
                ans += 1
                break
            elif tempSum < numbers[i]:
                left += 1
            else:
                right -= 1
    print(ans)


solution()