[G4] 백준 1253번 좋다 C++ 투 포인터

리뷰

 

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

set + map + 이분 탐색으로 접근했다가 자꾸 70%에 틀려서 투 포인터로 시도했더니 바로 AC되었다.

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있는 개수를 출력하는 문제

 

전역 변수

• n : 주어지는 정수의 개수
• ans : 정답을 저장할 변수
• nodes : 주어진 정수의 정보를 저장할 배열, 최대 크기는 2000이다.

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, nodes배열에 n개의 정수를 입력 받아준다.
2. nodes배열을 오름차순으로 정렬해 준다.
3. n번의 반복문을 수행해 주고, l을 0으로 r을 n - 1로 초기화 해준다.
4. l이 r보다 작을 경우 반복문을 계속 수행해 준다.
5. 만약 l이 i와 같다면 l을 증가시키고 continue, r이 i와 같다면 r을 감소시키고 continue 처리해 준다.
6. 만약 nodes[l] + nodes[r]이 nodes[i]와 같다면 ans를 증가시키고 break 처리해 준다.
7. nodes[i]보다 크다면 r을 감소시키고, 작다면 l을 증가시킨다.
8. 모든 탐색을 마친 후 ans에 저장된 값을 출력해 준다.

 

참고 사항

• 수의 위치가 다르면 값이 같아도 다른 수이다.
• N(1 ≤ N ≤ 2,000), (|Ai| ≤ 1,000,000,000, Ai는 정수)
• 임의의 수 Ai, Aj를 더했을 때 Ai와 Aj의 합이 Ai 혹은 Aj가 나오는 경우는 둘 중에 하나가 0인 경우이다.
• 해당 케이스를 잘 생각을 한다면 투 포인터가 아닌 다른 방식으로 접근이 가능해 보인다.

 

정답 코드

#include<iostream>
#include<algorithm>
using namespace std;

int n, ans;
int nodes[2000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) cin >> nodes[i];

	sort(nodes, nodes + n);
	for (int i = 0; i < n; i++) {
		int l = 0, r = n - 1;
		while (l < r) {
			if (l == i) {
				l++;
				continue;
			}
			else if (r == i) {
				r--;
				continue;
			}

			if (nodes[l] + nodes[r] == nodes[i]) {
				ans++;
				break;
			}
			else if (nodes[l] + nodes[r] > nodes[i]) r--;
			else l++;
		}
	}
	cout << ans;
}