[백준/python] 3273번 두 수의 합

1. 문제

2. 풀이

[접근 1 - 수학적 접근..?]

시간초과가 계속 났다 ㅠㅠ

x // 2 의 값보다 작은 수만 가지고 새 배열을 만들었다.

여기에서 각각의 수를 x에서 뺀 값이 기존 배열에 있으면 개수를 추가!

처음에 시간초과가 나고 시간을 줄이기 위해 시도한 것

1. sys.stdin.readline 사용하기

2. sort해서 배열의 x//2 번째 원소까지만 확인하기

3. List 의 In 보다는 Set의 In이 더 시간복잡도가 낮기 때문에 set으로 바꿔주기

 

등등 방법을 시도하였으나 모두 시간초과가 발생했다.

이건 알고리즘이 필요한 문제였던 거다ㅠㅠ

 

[접근 2 - 투포인터]

백준 문제 아래에 있는 알고리즘 보기를 눌러 투포인터라는 힌트를 얻어냈다.

수열을 sort한 뒤에 왼쪽, 오른쪽 끝부터 시작해서 계속 포인터를 움직이는 방법.

그러다가 왼쪽이 오른쪽 보다 커지면 반복문이 끝난다.

포인터를 움직이며 x 값에 도달하면 sum을 추가하는 방식으로 문제를 해결하였다.

 

3. 코드

[접근 1] - 시간초과

import sys
input = sys.stdin.readline

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

arr.sort()
# x를 2로 나눈 몫 보다 작은 수로 new_arr 만들기
new_arr = set([num for num in arr[:x//2] if num < x // 2])
sum = 0
#new_arr에 있는 수를 x에서 뺀 값이 arr에 있는 경우 개수 추가
for num in new_arr:
    if (x-num) in set(arr):
        sum += 1

print(sum)

[접근 2]

import sys
input = sys.stdin.readline

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

sum = 0
l, r = 0, n-1 #왼쪽, 오른쪽 투 포인터
while l < r:
    temp = arr[l] + arr[r]
    if temp == x: #x 값일 경우 sum 증가, 왼쪽 포인터 옮기기
        sum += 1
        l += 1
    elif temp < x: #왼쪽 포인터 옮기기
        l += 1
    else: #오른쪽 포인터 옮기기
        r -= 1

print(sum)

 

 

4. 결과

 

결과는 같아도 시간 초과가 나지 않도록 문제를 풀어야한다.

모든 문제는 일단 알고리즘을 사용해보자!

특히 이 문제처럼 입력값이 클 때는...