[백준] 1940 주몽

[백준] 1940 주몽

• https://www.acmicpc.net/problem/1940

• 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다.
  -> M 이상이 되면 갑옷이 만들어지는 것이 아닌, 정확이 M이 되어야 함에 주의!

풀이 1

• 투 포인터 알고리즘 이용

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

typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ll N, M;
	cin >> N >> M;
	
	vector<ll> vec;
	for (int i = 0; i < N; ++i) {
		ll input;
		cin >> input;
		vec.push_back(input);
	}

	//vec 오름차순 정렬
	sort(vec.begin(), vec.end());

	//투포인터 알고리즘
	ll sum;
	int cnt = 0;
	int left = 0;
	int right = N - 1;

	//sum = vec[left]+vec[right]
	//sum < M : left 오른쪽으로 이동
	//sum > M : right 왼쪽으로 이동
	//sum == M: left 오른쪽으로 이동 & right 왼쪽으로 이동 & cnt++
	while (left < right) {
		sum = vec[left] + vec[right];
		if (sum < M) {
			left++;
		}
		else if (sum > M) {
			right--;
		}
		else {
			left++;
			right--;
			cnt++;
		}
	}

	cout << cnt;
	return 0;
}

풀이 2

• set 자료구조 이용

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<int> vec;
	for (int i = 0; i < N; ++i) {
		int input;
		cin >> input;
		vec.push_back(input);
	}
	sort(vec.begin(), vec.end());

	int answer = 0;
	set<int> matchSet;
	for (int i = 0; i < N; ++i) {
		if (matchSet.find(vec[i]) != matchSet.end()) {
			answer++;
		}
		else {
			int match = M - vec[i];
			matchSet.insert(match);
		}
	}
	cout << answer;
	return 0;
}