백준 1037: 약수

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

1037번: 약수

 

아이디어

가장 작은 원소와 가장 큰 원소를 곱하면 N을 구할 수 있다.

 

구현 방법에 대한 고민

priority_queue와 vector

먼저 min과 max를 구해야 했다. 처음에는 vector 컨테이너에 담아서 sorting을 해서 첫 번째 원소와 마지막 원소를 읽어 오는 방법이 떠올라 코드를 작성하고 있었는데, 문득 "sorting할 필요가 없는 컨테이너를 사용하면 더 효율적이지 않을까?" 라는 생각이 들어 priority_queue를 사용하게 되었다.

그런데 제출 결과 두 방식의 메모리, 시간 차이는 없음을 알 수 있었다. ㅎㅎ

 

priority_queue 사용

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

int main()
{
	cin.tie(0);

	int div_cnt = 0;
	cin >> div_cnt;
	
	priority_queue<int, vector<int>> pq;
	priority_queue<int, vector<int>, std::greater<int>> pq_greater;

	for (int i = 0; i < div_cnt; i++) {
		int key;
		cin >> key;
		pq.push(key);
		pq_greater.push(key);
	}
	int min = pq.top();
	int max = pq_greater.top();

	int result = min * max;
	cout << result << "\n";
}

 

vector 사용

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

int main()
{
	cin.tie(0);

	int div_cnt = 0;
	cin >> div_cnt;
	
	vector<int> v(div_cnt);

	for (int i = 0; i < div_cnt; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());

	int min = v[0];
	int max = v[div_cnt - 1];

	int result = min * max;
	cout << result << "\n";
}