[백준/C++] 1253. 좋다

문제

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

1253번: 좋다

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

예제 입력 

10

1 2 3 4 5 6 7 8 9 10

예제 출력 

8

풀이

1. 주어진 배열을 오름차순으로 정렬한다.

2. idxs<숫자, 인덱스>, counts<숫자, 등장 횟수>, isGood<숫자, 좋은숫자 여부> map을 만든다. 

- counts : 같은 숫자가 여러번 등장했을 경우를 위해

- isGood : 한 번 좋은숫자가 된 이후로 중복으로 세어주지 않기 위해

3. 이중포문으로 주어진 배열을 돌면서 두 수의 합(temp)을 구한다.

3-1. 두 수의 합이 주어진 배열에 존재하고, 이전에 좋은숫자가 된 적이 없으면, 좋은 숫자의 개수를 counts[temp] 만큼 늘려준다.

 

- 시간복잡도를 조금이라도 줄이기 위해 이중 포문을 0~N, 0~N으로 돌리지 않고 0~N, i~N으로 돌렸다. 그래서 이를 위해 주어진 배열을 정렬해줬는데, 정렬을 하지 않고 제출을 해도 정답이 되어서 의아했다. 

- 문제에 명시되어 있지는 않지만 숫자가 오름차순으로 입력되는 모양이다.

 

코드

#include <map>
#include <vector>
#include <algorithm>
#include <iostream>

#define endl '\n'

using namespace std;

int N;
vector<int> nums;
map<int, int> idxs; // <숫자, 인덱스>
map<int, int> counts; // <숫자, 등장 횟수>
map<int, bool> isGood;

int main() {
	ios::sync_with_stdio(false); cin.tie(NULL);
	cin >> N;
	int input;
	for (int n = 0;n < N;n++) {
		cin >> input; nums.push_back(input);
	}
	//sort(nums.begin(), nums.end()); // ??
	for (int n = 0;n < N;n++) {
		idxs[nums[n]] = n;
		counts[nums[n]]++;
		isGood[nums[n]] = 0;
	}
	int result = 0;
	for (int i = 0;i < N;i++) {
		for (int j = i + 1;j < N;j++) {
			int temp = nums[i] + nums[j];
			//nums에서 이 값과 같은것이 있는지 확인
			if (idxs.count(temp) && !isGood[temp]) {
				//인덱스가 다른지 확인 
				if (idxs[temp] != i && idxs[temp] != j) {
					result += counts[temp];
					isGood[temp] = 1;
				}
			}
		}
	}
	cout << result << endl;
	return 0;
}

 

결과