문제
n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
출력
문제의 조건을 만족하는 쌍의 개수를 출력한다.
예제
나의 풀이1
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, input().split()))
X = int(input())
cnt = 0
for i in range(N-1):
for j in range(i+1, N):
if S[i] + S[j] == X:
cnt += 1
print(cnt)- 생각나는 대로 풀었는데 시간 초과로 실패했다.
나의 풀이2
import sys
input = sys.stdin.readline
N = int(input())
S = list(map(int, input().split()))
X = int(input())
S.sort()
cnt = 0
for i in range(N):
if S[i] < (S[-1] // 2):
continue
remainder = X - S[i]
if remainder in S:
cnt += 1
print(cnt)- 입력받은 정수들을 정렬한 후에
x를 만족할 수 있는 다른 수가 있는지 찾는 방법으로 풀어봤지만 또 다시 시간 초과로 실패했다.
투 포인터 (Two Pointers) 알고리즘
투 포인터란?
- 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘
- 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색한다
- 시간복잡도: O(N)
투 포인터 동작 방식과 예시
- 현재 수열의 시작과 끝을 가리키는
start,end2개의 포인트를 생성한다. - 처음에는
start=end=0이고, 두 포인터들의 관계는start <= end이다
- 특정한 합을 가지는 부분 연속 수열 찾기: 리스트의 연속 수열의 합이 특정 값을 가지는 것을 확인하는 문제
- 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 한다.
- 현재 부분 합이 M과 같다면 카운트한다.
- 현재 부분 합이 M보다 작다면 end를 1 증가시킨다.
- 현재 부분 합이 M보다 크거나 같다면 start를 1 증가시킨다.
- 모든 경우를 확인할 때까지 2-4번 과정을 반복한다.
다른 사람의 풀이
import sys
input = sys.stdin.readline
N = int(input())
S = sorted(list(map(int, input().split())))
X = int(input())
left, right = 0, N-1
cnt = 0
while left < right:
sum = S[left] + S[right]
if sum == X:
cnt += 1
left += 1
right -= 1
elif sum > X:
right -= 1
elif sum < X:
left += 1
print(cnt)- 정석적인 투 포인터 동작 방식과는 부합하지 않지만 투 포인터 알고리즘을 사용한 풀이 방법이다.
- 입력받은 정수들을 오름차순으로 정렬하고 포인터를 리스트의 양쪽 끝에 생성해서 조건 충족 여부에 따라 안쪽으로 들어가면서 두 포인터가 만나면 반복문을 종료한다.
- 두 수의 합이 타겟 값과 일치한다면 카운트를
1증가시키고, 두 포인터를 모두 안쪽으로 한 칸씩 이동한다. - 두 수의 합이 타겟보다 크다면 합을 줄이기 위해 오른쪽 포인터를 안쪽으로(왼쪽으로) 한 칸 이동한다.
- 두 수의 합이 타켓보다 작다면 합을 늘리기 위해 왼쪽 포인터를 안쪽으로(오른쪽으로) 한 칸 이동한다.
- 두 수의 합이 타겟 값과 일치한다면 카운트를