[Python] 백준 3273 두 수의 합

 

문제 분석

• n개의 양의 정수가 주어졌을 때
• 이 중 두 수를 더해 x를 만족하는 쌍의 개수 출력

 

코드 설계

• 완탐?
• 앞에서부터 하나 픽(a)하고 나머지 중에 (나머지인데 인덱스 값이 더 큰 값들)
• x - a 인 값이 있는지 확인
• 있으면 cnt += 1

 

정답 코드

1차 - 시간초과

import sys
input = sys.stdin.readline

n = int(input())
arr = sorted(list(map(int, input().split())))
x = int(input())

cnt = 0

for i in range(0, n-1) :
    if arr[i] >= x :
        continue
    if (x - int(arr[i])) in arr[i+1:] :
        cnt += 1
print(cnt)

 

다른 사람 코드 1 - 투 포인터

import sys
input = sys.stdin.readline

n = int(input())
numbers = sorted(list(map(int, input().split())))
x = int(input())

cnt = 0
left, right = 0, n-1

while left < right :
    tmp = numbers[left] + numbers[right]
    if tmp == x : 
        cnt += 1
        left += 1
    elif tmp < x :
        left += 1
    else :
        right -= 1
print(cnt)

** 투포인터

1. 두 수의 합이 x보다 큰 경우 - 더 큰 값을 더해야하므로 left+1
2. 두 수의 합이 x보다 작은 경우 - 더 작은 값을 더해야하므로 right-1
3. 두 수의 합이 x인 경우 - answer+1 & left+1

투 포인터 탐색은 왼쪽, 오른쪽 방향의 인덱스가 서로 만날 때(교차할 때)까지 진행

 

다른 사람 코드 2

import sys

n = int(sys.stdin.readline())
a = set(map(int, sys.stdin.readline().split(" ")))
x = int(sys.stdin.readline())
count = 0

for i in a:
    j = x - i
    if j in a:
        count += 1

print(int(count/2))

다만 (1, 3) (3, 1) 과 같이 두번씩 카운트 되므로 i<j 를 체크해주거나 카운트를 절반으로 나누어주면 된다.

 

 

2회차 - 25.02.07

• 자연수 x가 주어졌을 때, 두 수의 합이 x가 되는 쌍의 수를 구하는 프로그램을 작성하라
• 쌍 → 순서 상관 x
• 제한시간 1초 : 연산 1억번 → 2중 for문을 돌면 시간초과

 

1차 - 시간 초과

import sys
input = sys.stdin.readline

n = int(input())
nums = list(map(int, input().split()))
x = int(input())

ans = 0

for n in nums :
    if x-n in nums :
        ans += 1
        del nums[nums.index(n)]
        del nums[nums.index(x-n)]
        
print(ans)

 

2차 - 시간 초과

정렬 → 이분탐색?

import sys
input = sys.stdin.readline

def isExist(n, arr) :
    # 종료조건
    if len(arr) == 1 and n not in arr :
        return False

    mid = len(arr) // 2
    if n == arr[mid] :
        return True

    if n < arr[mid] :
        return isExist(n, arr[:mid])
    elif n >= arr[mid] :
        return isExist(n, arr[mid:])

n = int(input())
nums = list(map(int, input().split()))
x = int(input())

nums = sorted(nums) # 정렬

ans = 0
for n in nums :
    if isExist(x-n, nums) :
        ans += 1
        del nums[nums.index(n)]
        del nums[nums.index(x-n)]

print(ans)

 

리펙토링..

import sys
input = sys.stdin.readline

# def isExist(n, arr) :
#     # 종료조건
#     if len(arr) == 1 and n not in arr :
#         return False
# 
#     mid = len(arr) // 2
#     if n == arr[mid] :
#         return True
# 
#     if n < arr[mid] :
#         return isExist(n, arr[:mid])
#     elif n >= arr[mid] :
#         return isExist(n, arr[mid:])

def isExist(n, arr):
    if not arr:  # 배열이 비었으면 False 반환
        return False

    mid = len(arr) // 2
    if n == arr[mid]:
        return True

    return isExist(n, arr[:mid]) if n < arr[mid] else isExist(n, arr[mid:])

n = int(input())
nums = list(map(int, input().split()))
x = int(input())

nums = sorted(nums) # 정렬

ans = 0
for n in nums :
    if isExist(x-n, nums) :
        ans += 1
        del nums[nums.index(n)]
        del nums[nums.index(x-n)]

print(ans)

왜 시간초과가 날까?

 

nums = sorted(nums)  # O(N log N)

→ 파이썬 정렬의 시간복잡도는 O(N log N)

for n in nums:  # O(N)
    if isExist(x - n, nums):  # O(log N)
        ans += 1
        del nums[nums.index(n)]  # O(N)
        del nums[nums.index(x - n)]  # O(N)

• for n in nums: → nums의 길이가 N이므로 최악의 경우 O(N) 번 반복
• isExist(x - n, nums) → 이진 탐색(O(log N)) 수행
• nums.index(n)와 nums.index(x - n) → 각각 O(N) (리스트에서 값 찾기)
• del nums[...] → 리스트 요소 삭제는 O(N)

 

투포인터 by chatGPT

nums.sort()  # O(N log N)

left, right = 0, len(nums) - 1
ans = 0

while left < right:
    s = nums[left] + nums[right]
    if s == x:
        ans += 1
        left += 1
        right -= 1
    elif s < x:
        left += 1
    else:
        right -= 1

✅ 정렬 후 O(N log N) + 투 포인터 O(N) → 최종 O(N log N)
✅ N이 100,000이어도 충분히 1초 안에 실행 가능!

 

3회차 - 25.02.14

문제 유형 : 투 포인터

import sys
input = sys.stdin.readline

n = int(input())
pro = sorted(list(map(int, input().split())))
x = int(input())

right = len(pro)-1
left = 0
ans = 0

while(left < right) :
    if pro[left] + pro[right] == x :
        ans += 1
        left += 1
        # right -= 1
    elif pro[left] + pro[right] < x :
        left += 1
    else :
        right -= 1
print(ans)