[BOJ] 백준 3273 두 수의 합 (Swift)

문제

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

3273번: 두 수의 합

풀이

n의 갯수가 최대 10만이기 때문에, 이중 for문으로 풀이할 시 시간초과$(O(n^2))$가 날 것입니다.
따라서 정렬$(O(nlogn))$ + 투 포인터 $(O(n))$ 알고리즘으로 풀이할 수 있습니다.

오름차순으로 정렬해 준 뒤, 첫번째 index를 start, 마지막 index를 end로 설정해줍시다.

array[start] + array[end] 값이 x보다 작으면, start 값을 1 늘려주어 더 큰 값으로 갖도록 하고,
x보다 크다면 end 값을 1 줄여주어 합이 더 작도록 구현합시다.

만약 x와 같다면 조건을 만족하므로, 쌍의 개수를 늘려줍시다.
또한 만족하는 조건을 찾았으므로 start를 1늘려주고, end값도 1을 줄여줍시다.

소스코드

후기

투 포인터 알고리즘을 학습하는 기초적인 문제라고 생각했습니다.