참고한 답을 이해하고 해석한 글입니다.

Intuition

주어진 수열 상에서 특정 조건을 만족하는 숫자가 존재하는지를 찾는 문제이다. 어떤 숫자를 찾아야 할지 알고, 정렬된 수열 상에서 해당 숫자를 찾는 빠른 방법은 이분탐색 또는 투포인터를 활용할 수 있다.

Algorithm

1. 이분탐색이나 투포인터를 활용하기 위해서는 입력받는 수열을 정렬해줘야 한다.
2. 수열의 element를 순회하면서 해당 element를 제외한 다른 숫자 두 개의 합으로 해당 요소의 값을 만들 수 있는지 찾는다. 이를 빠르게 수행하기 위해 이분탐색을 이용하여 left, right 변수의 합을 해당 요소의 값과 비교한다.

본인의 경우, 이분탐색을 사용하고자 했다. 더하기의 기준이 될 값을 순회를 통해 지정해두고, 피연산자를 이분탐색으로 찾고자 했었다. 이 풀이는 O(N^2logN)이라 N이 최대 2000인 이 문제에서는 TLE가 안날 거라 생각했는데 시간초과가 발생했다. 알아보니 **슬라이싱을 수행하기 위해서 슬라이스 길이가 k라고 할 때, O(K)만큼의 시간이 걸린다고 한다. 그렇다면 O(N^3logN)이 되어버려서 시간초과가 이해된다.** 결국, 답지를 참고했고 마치 이분탐색처럼 생긴 투포인터 로직을 학습할 수 있었다.

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(n):
        left, right = 0, len(li)-2
        temp = li[:i] + li[i+1:]
        while left < right:
            v = temp[left] + temp[right]
            if v == li[i]:
                ans += 1
                break
            elif v < li[i]:
                left += 1
            else :
                right -= 1

    print(ans)

Complexity Analysis

• Time Complexity : O(N^2)
• Space Complexity : O(N)

Try Log

• 이분탐색(오답)
  • 시간복잡도 O(N^3*logN)
  • 공간복잡도 O(N)

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    n = int(input())
    li = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(n):
        for j in range(i):
            has_found = False
            target = li[i]
            operand = li[j]
            temp = li[:j] + li[j+1:i] + li[i+1:]
            left, right = 0, len(temp) - 1
            if left == right and temp[left] + operand == target:
                ans += 1
            else:
                while left < right:
                    mid = (left + right) // 2
                    if temp[mid] + operand == target:
                        has_found = True
                        break
                    elif temp[mid] + operand < target:
                        left = mid + 1
                    else:
                        right = mid
                if has_found:
                    ans += 1
                    break

    print(ans)