[백준/BOJ][Python] 3273번 두 수의 합

[백준/BOJ][Python] 3273번 두 수의 합

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

 

---

아이디어

 

2년 전 C++로 풀다가 시간 초과, 1년 전 python으로 풀다가 시간초과나서 묵혀뒀던 문제이다

(사실 3일 전에 풀었는데 이제야 올린다..ㅎ)

 

문제는 정말 간단하다. 배열 주어지고 x가 주어졌을 때 배열에서 합이 x가 되는 쌍의 개수를 구하면 된다.

근데 시간 초과인 이유는 이중for문으로 O(n^2) 대충 n의 최댓값은 100,000이니까 n^2이면 10,000,000,000 ㄷㄷ

 

암튼 투포인터로 풀면 간단하게 풀 수 있다.

처음에 투포인터라고 해서 이름이 무서워서 두려웠는데 C언어의 그 포인터가 아니었다ㅋㅋㅋ

그냥 인덱스 2개로 움직이는 것이다

 

이 문제는 맨 처음 인덱스(start), 맨 마지막 인덱스(end)로 정하고

둘의 합이 주어진 x보다 크면 start 인덱스를 오른쪽으로 (+1) 작으면 end 인덱스를 왼쪽으로 (-1) 움직이면 된다.

만약 합이 x가 나왔다면 cnt + 1 하면 끝!!!

 

+) 그냥 갑자기 함수로 풀고 싶어서 함수로 풀었다

 

 

 

 

---

코드

import sys
input = sys.stdin.readline

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

start = 0
end = len(arr) - 1
cnt = 0
arr.sort()

def Two_pointer(x):
    start = 0
    end = len(arr) - 1
    cnt = 0
    while start < end:
        sum = arr[start] + arr[end]
        if sum == x:
            cnt += 1
        if sum <= x:
            start += 1
        else:
            end -= 1
    return cnt

print(Two_pointer(x))

sort()가 O(nlogn)이기 때문에 이 코드의 시간 복잡도는 O(nlogn)