백준 실버3 문제입니다. 실전에 대비하기 위해 60분 시간제한을 두고 풀었습니다.
문제
https://www.acmicpc.net/problem/3273
[나의 풀이]
⌛ 12분
n = int(input())
arr = list(map(int,input().split()))
x = int(input())
ans = 0
arr.sort()
front = 0
rear = len(arr)-1
while front<rear:
tmp = arr[front]+arr[rear]
if tmp==x:
ans += 1
rear -= 1
elif tmp<x:
front += 1
else:
rear -= 1
print(ans)
정수로 이루어진 N 크기의 배열이 주어지고, 해당 배열 중 2개 요소의 합이 특정 값(X)을 만족하는 경우의 수를 구하는 문제입니다.🐝🐝🐝
투 포인터 알고리즘을 활용하되, 문제의 요구에 따라 일정 범위의 값을 연산하는 것이 아닌 시작(front)/끝(rear) 인덱스의 요소를 두가지만 덧셈 연산하는 방식으로 구현하였습니다.
[다른 사람의 풀이1]
n = int(input())
a = list(map(int, input().split()))
x = int(input())
answer=0
a.sort()
for i in range(n):
for j in range(i+1,n):
if a[i] + a[j] == x:
answer+=1
if a[i] + a[j] > x:
break
print(answer)
투 포인터 알고리즘 대신, 직관적으로 2중 loop문을 통해 정렬된 배열(a)에서 두 요소를 모두 파악하며 해결한 풀이입니다.🐇🐇🐇
[다른 사람의 풀이2]
import sys
n = int(input())
numbers = sorted(list(map(int, sys.stdin.readline().split())))
x = int(input())
answer = 0
left, right = 0, n-1 # 왼쪽, 오른쪽
while left < right:
temp = numbers[left] + numbers[right]
if temp == x:
answer += 1
left += 1
elif temp < x:
left += 1
else:
right -= 1
print(answer)
'나의 풀이'와 같이 시작 인덱스(left)/끝 인덱스(right)를 기준으로 하는 투 포인터 알고리즘을 통해 구현한 풀이입니다.🦘🦘🦘
감사합니다.