3273번 - 두 수의 합

💡 조합 & 투포인터 다시 확인하기!!

< 오답 코드 >

from itertools import combinations

n = int(input())

num = list(map(int, input().split(' ')))

comb = list(combinations(num,2))

print(comb)

count = 0

for a,b in comb:
    if (a + b == 13):
        count += 1
        
print(count)

• 이론상은 맞는 거 같고, 테스트 코드도 통과하였지만, 시간초과가 발생하였다.
• 아무래도 조합을 찾아야 하다보니, n이 100000일 경우에 너무 많은 수의 쌍이 리스트에 저장되기 때문에 "메모리 초과" 오류가 발생했던 거 같다.

<오답코드>

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

count = 0
start = 0
end = n-1

while(start < n-1):
    
    if num[start] + num[end] == x:
        count += 1
    
    if start == end:
        start += 1
        end = n-1
    else:
        end -= 1
    
print(count)
    

• 나름 투포인터를 이용해서 구해보려고 하였으나, 실질적으로 구현한 것은 for문이 2개와 같은 O(n^2)이다..ㅎ
• 투포인터로 범주를 점점 줄일 수 있는 방식을 고려해 봐야겠다고 생각했다.

<정답코드>

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

count = 0
start = 0
end = n-1

# 오름차순 정렬
num.sort()

while(start < end):
    
    result = num[start] + num[end]
    
    if result == x:
        start += 1
        count += 1
    elif result < x:
        start += 1
    else:
        end -= 1
    
print(count)

• 투포인터를 이용하는 방식을 "오름차순 정렬"을 통해서 이용하였다.
• 오름차순 정렬을 하여 start는 작은 쪽을 end는 큰쪽을 가르키도록 설정하였다.
• num[start] + num[end]의 합을 통해서 x값과 크기를 비교하여 범주를 줄이는 방식을 사용하였다.
• 만약 합이 x보다 작다면 start쪽을 늘려주면 자동으로 숫자가 커지니 start += 1을 하였고, 합이 x보다 크면 end쪽을 줄여주면서 맞춰주어 범위를 줄여나갔다.

💡 코딩테스트 중 나온 기발한 접근법

• 서현님

n = int(input())
seq = input().split()
x = int(input())

max_value = 1000000
arr = [0] * (max_value + 1)

result = 0

for i in range (0, n):
    num = int(seq[i])
    y = x - num
    if 0 <= y <= max_value and arr[y] == 1:
        result += 1
        arr[num] = 1
    else:
        arr[num] = 1
print(result)

• 정렬보다 훨씬 시간복잡도가 작은 코드입니다. (정렬 : O(nlogn) 이코드: O(n))
• 1 + 12 = 13일 때, arr[1] 과 arr[12]를 1로 해주고 만약 12가 오면 arr[12]는 이미 1이기 때문에 +1을 해준다.