[BOJ][Python] 3273번 - 두 수의 합[정렬- 실버 3티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 두수의 합

링크: 두 수의 합

문제설명

예제 입력 

9
5 12 7 10 9 1 2 3 11
13

예제 출력

3

그리디 탐색의 냄새가 나는 문제다

모든 조건을 확인하는 문제로서, 원하는 답이 나오는 경우의 수를 찾아주면 된다.

처음에 문제를 보고 in을 사용하여 풀려고 했으나, 시간초과가 나오게 되어서 투포인터 방식으로 다시 도전해서 풀었다.

📃 소스코드 및 설명(시간초과)

n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort()
x = int(input())
count = 0
# 정렬을 시킨후 루프를 돌면서 해당 검출하고자 하는 숫자를 제외한 나머지에서 찾는 방식으로 접근
# 시간초과로 인해 실패하였다..ㅠ
for i in numbers:
  if x-i in numbers[i:]:
    count+=1
print(count)

📃 소스코드 및 설명(투포인터 방식)

import sys
n = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))
numbers.sort()

x = int(input())

# 투 포인터 방식으로 첫점과 끝점을 지정해주고, 첫점부터 끝점까지 루프를 돌면서
# 내가 찾는 답이 있는가 없는가를 탐색하는 방식이다.
start_pos = 0
end_pos = len(numbers)-1
count = 0

# 같은 수(같은 리스트의 index)를 더하는일이 없도록,
# 교차하는 경우도 제외하고 작을경우만 while을 돌려준다.
while start_pos < end_pos:
  if numbers[start_pos]+numbers[end_pos] == x:
    start_pos += 1
    count+=1
  elif numbers[start_pos]+numbers[end_pos] < x:
    start_pos += 1
  else:
    end_pos-=1
print(count)