문제
풀이
모든 합을 저장하여 이분 탐색으로 진행할 경우, 자기 자신이 합에서 사용되었는지 알 수 없기에 사용할 수 없다.
unordered_map 사용
- 모든 합을 피연산자와 함께 unordered_map에 저장한다.
- input이 unordered_map에 있는지 확인하고, 피연산자로 자기 자신이 사용되었는지 확인한다.
두 포인터 사용
- 입력된 수열을 정렬하고 양 옆에서 두 포인터 알고리즘을 시작한다.
- 같은 수가 합에 사용되면 안 되므로 start < end일 때까지만 반복한다.
- 자기 자신은 합에 포함되면 안 되므로 start와 end를 조정
코드
unordered_map 사용
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
vector<int> inputs;
unordered_map<int, vector<pair<int, int>>> sums;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int temp;
cin >> temp;
inputs.push_back(temp);
}
// 가능한 모든 경우를 unordered_map에 저장
for (int i = 0; i < N; ++i)
{
for (int j = i + 1; j < N; ++j)
{
// 합과 함께 피연산자들을 저장한다.
sums[inputs[i] + inputs[j]].push_back(make_pair(i, j));
}
}
int answer = 0;
for (int i = 0; i < N; ++i)
{
// inputs[i]가 unordered_map에 있는지 확인
int find_num = inputs[i];
if (sums.find(find_num) != sums.end())
{
bool flag = false;
for (auto operand : sums[find_num])
{
// 피연산자로 자기 자신이 들어있는지 확인
if (operand.first != i && operand.second != i)
{
flag = true;
break;
}
}
if (flag)
{
answer++;
}
}
}
cout << answer;
return 0;
}
두 포인터 사용
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> inputs;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
int temp;
cin >> temp;
inputs.push_back(temp);
}
sort(inputs.begin(), inputs.end());
int answer = 0;
for (int i = 0; i < N; ++i)
{
int find_num = inputs[i];
int start = 0;
int end = inputs.size() - 1;
// 두 수가 같으면 안 되므로 start < end일 때 까지만 반복
while (start < end)
{
// 자기 자신은 합에 포함되면 안된다.
if (start == i)
{
start++;
continue;
}
if (end == i)
{
end--;
continue;
}
// 합이 find_num과 같을 경우 answer 증가
int sum = inputs[start] + inputs[end];
if (sum == find_num)
{
answer++;
break;
}
// 합이 더 작을 경우 start 증가
// 합이 더 클 경우 end 감소
if (sum < find_num)
{
start++;
}
else
{
end--;
}
}
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 3649: 로봇 프로젝트 (1) | 2023.10.29 |
---|---|
[백준][C++] 8983: 사냥꾼 (1) | 2023.10.28 |
[백준][C++] 3020: 개똥벌레 (0) | 2023.10.26 |
[백준][C++] 2343: 기타 레슨 (1) | 2023.10.26 |
[백준][C++] 16564: 히오스 프로게이머 (1) | 2023.10.23 |