문제
양의 정수 집합에서 어떤 원소의 정확히 두 배인 원소가 존재하는 쌍의 개수를 구하라.
입력
0이 입력될 때까지 수를 읽어 한 집합으로 구성한다. -1이 입력되면 프로그램을 종료한다.
출력
각 집합에서 (x, 2x) 쌍의 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 2 3 4 0 -1 | 2 |
풀이
모든 쌍을 확인하여 두 배 관계를 센다.
- 0이 나올 때까지 수를 배열에 저장한다
- 이중 반복으로
num[i] == num[j] * 2인 쌍을 센다 - -1이 입력되면 전체 종료한다
핵심 아이디어: 집합 크기가 작으므로 O(N^2) 브루트포스로 모든 쌍을 확인하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
vector<int> num;
int ans;
int main()
{
while (1)
{
int x;
cin >> x;
if (x == -1)
break;
if (x)
{
num.push_back(x);
continue;
}
for (int i = 0; i < num.size(); i++)
for (int j = 0; j < num.size(); j++)
if (num[i] == num[j] * 2)
ans++;
cout << ans << '\n';
num.clear();
ans = 0;
}
}복잡도
- 시간: O(N^2) (N: 집합 크기)
- 공간: O(N)