[G4] 백준 2295번 세 수의 합 C++ 해시맵, 브루트포스 알고리즘

리뷰

 

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

해시맵과 브루트포스 알고리즘을 통해 풀이한 문제

수열 U의 원소가 2억보다 작거나 같은 자연수 이기 때문에 일반 배열로는 사용이 불가능하다.

브루트포스 말고 이분 탐색으로도 접근 해봤는데 왠지 모르겠지만 AC를 받지 못해 그냥 완탐을 돌렸다.

 

 

전역 변수

• n : 수열의 길이를 저장할 정수형 변수
• U : 수열을 저장하기 위한 정수형 벡터
• dic : 임의의 두 원소의 값을 key로, 존재 여부를 value로 저장하기 위한 해시맵

 

함수

없음

 

 

문제풀이

1. n값을 입력 받고, U를 n만큼 크기를 resize해준다.
2. U에 n개의 원소를 입력 받은 뒤에 오름차순으로 정렬해준다.
3. 수열 U를 2번 참조하여 중복이 가능하도록 임의의 두 원소를 더한 값을 key로 dic에 기록해 준다.
4. 수열 U를 뒤에서 부터 참조하여 각 원소를 정수형 변수 target에 저장해 준다.
5. 다시 한번 i까지의 for문을 실행하고 target - U[j]가 dic에 존재하는지 체크해 준다.
6. 만약 존재한다면 해당 target이 정답이 된다, 해당 수를 출력해 주고 탐색을 중단한다.

 

참고 사항

수열 U를 뒤에서 부터 탐색해 주는 것이 가장 그리디한 선택인듯 하다.

이후 for문을 통해 완탐을 도는 부분은 이분 탐색을 통해 충분히 개선이 가능해 보인다.

 

 

정답 코드

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

int n;
vector<int> U;
unordered_map<int, int> dic;

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

	cin >> n;
	U.resize(n);
	for (int i = 0; i < n; ++i) cin >> U[i];
	sort(U.begin(), U.end());

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			dic[U[i] + U[j]]++;

	for (int i = n - 1; i >= 0; --i) {
		int target = U[i];
		for (int j = 0; j < i; ++j) {
			if (dic[target - U[j]]) {
				cout << target;
				return 0;
			}
		}
	}
}