[PS]#Ice Cream Parlor

---

 

https://www.hackerrank.com/challenges/icecream-parlor/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

Ice Cream Parlor | HackerRank

 

#include <bits/stdc++.h> 
using namespace std; 
#define PII pair<int, int>

bool Compare(const PII& v1, const PII& v2) 
{ 
	if (v1.second == v2.second) return true; 
	if (v1.first < v2.first) return true; 
	return false; 
}

vector<int> icecreamParlor(int m, vector<int> arr) 
{ 
	vector<int> res; 
	vector<PII> map; 
	for (int i = 0; i < arr.size(); ++i) 
	{ 
		map.push_back({ arr[i], i + 1 }); 
	} 
	priority_queue<int> pq; 
	sort(map.begin(), map.end()); 
	for (int i = 0; i < map.size(); ++i) 
	{ 
		int f = map[i].first, s = map[i].second; 
		int calc = m - f; 
		auto it = lower_bound(map.begin(), map.end(), PII(calc, s), Compare); 
		if (it == map.end() || (*it).first != calc) continue; 
		res.push_back(s); 
		res.push_back((*it).second); 
		break; 
	} 
	sort(res.begin(), res.end()); 
	return res; 
}

 

* 문제 풀이 과정

 

이분 탐색을 활용해 시간을 절약하는 문제이다.

STL 의 lower_bound 를 이용했다.

 

다만,

인덱스를 구해야한다는 것과 중복되는 값들을 어떻게 처리해야할 것인지 살펴봐야한다.