[3273] 두 수의 합 - 배열/투 포인터 ★☆☆☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

---

[ 문제 접근 ]

 

- 투 포인터 문제라고 카테고리에 나와 있는데 배열로 풀이 가능하다.

 

---

[ 배열 풀이 ]

 

#include<iostream>

using std::cout; using std::cin;

int n;
int cnt;
int arr[100001];
bool is_in[2000001];

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		is_in[arr[i]] = true;
	}
	int x;
	cin >> x;

	for (size_t i = 0; i < n; i++) {
		int res = x - arr[i]; // res 는 음수 일수도 있기 때문에 예외처리 해줘야한다.
		if (res>=0 && is_in[res]) cnt++;  
	}

	cout << cnt/2;

	return 0;
}

배열로 풀기는 했으나 문제를 잘 읽지 못해 몇번 틀렸다.

 

문제에서 

 

자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하시오.

 

i < j 를 간과하고 풀었다.  i, j 이기 때문에 중복되는 쌍은 제거해주기 위해 마지막에 /2 로 나눠줘야한다.

 

또한 i  < j 이기 때문에 입력 받으면서 is_in 배열을 true로 해줄게 아니라

 

  int ans = 0;
  cin >> n;
  for(int i = 0; i < n; i++) cin >> a[i];
  cin >> x;

  for (int i = 0; i < n; i++) {
    // x-a[i]가 존재하는지 확인
    if(x-a[i] > 0 && occur[x-a[i]]) ans++;
    occur[a[i]] = true;
  }
  cout << ans;
}

 

이런 식으로 탐색하면서 앞에꺼 부터 true로 바꿔줘도 된다.

( 어짜피 자신 인덱스보다 낮은 인덱스의 arr 값만 참조 하기 때문에 )

---

[ 투 포인터 풀이 ]

#include<iostream>
#include<algorithm>

using std::cout; using std::cin;

int n;
int cnt;
int arr[100001];

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> n;
	
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	int x;
	cin >> x;

	std::sort(arr, arr + n);

	int cnt = 0;
	int start = 0;
	int end = n - 1;

	while (start < end){   // start 랑 end 랑 같으면 종료
		int sum = arr[start] + arr[end];
		if (sum == x) {
			start++;
			end--;
			cnt++;
		}
		else if (sum > x) {
			end--;
		}
		else {
			start++;
		}
	}
	cout << cnt;

	return 0;
}

 

---

[ Key Point ]

 

👉 문제를 잘 읽자!

 

👉 투 포인터 풀이를 할때 while 문 탈 출 조건을 잘 살펴봐야한다. 부등호 하나로 틀리는 경우가 많다.

 

---

[ 다른 사람 풀이 ]

 

ref :: https://velog.io/@kpg0518/%EB%B0%B1%EC%A4%80-3273%EB%B2%88-%EB%91%90%EC%88%98%EC%9D%98-%ED%95%A9

ref :: https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x03/solutions/3273.cpp