[백준 알고리즘] 3273번: 두 수의 합 (Python / 파이썬)

 

문제 접근

이중포문을 돌리면 쉽게 풀 수 있지만, 시간초과가 날 것 같아 계산을 해봤다.

파이썬 기준 제한시간 1초 => 1*3+2 = 5초,

5 * 2000만번(연산) = 약 1억번 연산이 가능

n이 최대 10만이므로 O(n^2)의 알고리즘을 적용할 경우 최악의 경우 10,000,000,000(백억번)의 연산을 해야 한다.

즉 시간초과가 나므로 다른 방법을 사용하는데, 투 포인터 방법이 정석인 것 같고 파이썬의 경우 in 연산자로 푸는 것도 가능하다.

 

정답 코드 1 (투 포인터)

import sys

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

left = 0
right = n-1

while left < right:
    temp = a[left] + a[right]
    if temp == x:
        count += 1
        left += 1
    elif temp > x:
        right -= 1
    else: left += 1

print(count)

이분 탐색과 비슷하다. 오름차순 정렬이 되어있어야 한다.

왼쪽 끝과 오른쪽 끝을 설정하고,

기본적으로 left 인덱스를 +1 해주면서 합이 x인지 체크를 하되

두 합이 x보다 클 때만 right 인덱스를 -1 해준다.

이렇게 하면 리스트를 한 번 이하로 순회하고 모두 체크할 수 있게 되므로 O(n)의 시간 내로 문제를 해결할 수 있다.

 

정답 코드 2 (in 연산자 사용)

in은 시퀀스 객체에서 멤버가 있는지 체크하는 연산자인데 파이썬에서 기본적으로 지원한다.

hash로 구현되어 있어 체크하는 데 약 O(1)의 시간복잡도를 가진다.

따라서 아래처럼 구현할 수도 있다.

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 를 체크해주거나 카운트를 절반으로 나누어주면 된다.

속도는 비슷했다.

 

---

3273번: 두 수의 합