[map, set] map, set 정렬, 사용자 구조체 담기 / 문제 풀이: 샘플제품사진_LG swedu

map, set의 기본 정렬: 오름차순

map, set에 ket, value pair 또는 key를 삽입할 시 자동으로 오름차순 정렬된다.

#include <iostream>
#include <map>
#include <set>

using namespace std;

int main() {
	map<int, string> MAP;
	MAP.insert({ 2, "james" });
	MAP.insert({ 1, "jin" });
	MAP.insert({ 3, "tom" });

	for (auto iter = MAP.begin(); iter != MAP.end(); iter++) {
		cout << iter->first << ": " << iter->second << endl;
	}
}

내림차순 정렬로 바꾸기: greator<int>

내림차순 정렬로 바꾸고 싶다면 greator<int>를 사용한다. 여기서 int는 key의 자료형이다.

int main() {
	map<int, string, greator<int>> MAP;
	MAP.insert({ 2, "james" });
	MAP.insert({ 1, "jin" });
	MAP.insert({ 3, "tom" });

	for (auto iter = MAP.begin(); iter != MAP.end(); iter++) {
		cout << iter->first << ": " << iter->second << endl;
	}
}

set 자료구조도 value만 없을 뿐 위 방식과 동일하게 정렬된다.

---

set에 사용자 정의 자료형 담기

참고 사이트: https://ansohxxn.github.io/stl/mapsetcustom/

struct MyStruct {
	int num;
	string name;

	bool operator<(MyStruct other) const{
		if (this->num != other.num)
			return this->num < other.num;
		else
			return this->name < other.name;
	}
};

int main() {
	
	set<MyStruct> SET;
	SET.insert({ 2, "jin" });
	SET.insert({ 1, "james" });
	SET.insert({ 3, "tom" });

	for (auto iter = SET.begin(); iter != SET.end(); iter++) {
		cout << iter->num << ": " << iter->name << endl;
	}

	cout << (*SET.find({ 2, "jin" })).num << endl;
	cout << (*SET.find({ 2, "jin" })).name << endl;
	
}

---

문제: 샘플제품사진

source: https://swedu.lge.com/

문제 풀이 방법

1) 좌표 기준 오름차순 정렬한다.

2) 제품 타입이 몇가지인지 카운트한다.
1, 3, 7 총 3가지의 타입이 존재한다.

3) 제품의 갯수는 최대 50,000개이다. 따라서 아무리 복잡하여도 O(nLogn)의 시간복잡도로해결해야 한다.
이를 위해 제품하나씩 탐색하면서 for문 내부에는 O(Logn)의 시간복잡도 로직을 찾아야 한다.
=> map, set 자료구조를 활용한다.

3-1) 순차적으로 map, set 자료에 {id, loc}, {loc} 정보를 담는다.

3-2) 이미 map에 존재하는 id 제품을 다시 발견한다면 map, set에 해당 id의 위치정보를 갱신한다.

3-3) 새로운 id 제품 탐색 시 (3-1)과 동일한 작업을 한다.

3-4) map 자료구조의 크기가 제품 타입 가짓수와 동일해진다면, 즉 모든 제품이 map 자료구조에 들어오게 된다면 마지막에 들어온 위치 정보와 맨 처음 위치 정보(set의 오름차순 정렬을 활용)를 빼주어 길이를 구한다.

3-5) 3-1~4 작업을 반복하며 길이를 구할 수 있을 땐 그때마다 길이를 구하여 최소 길이를 갱신해간다.

결국 구한 length 중 가장 작은 값인 4가 정답이 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

int N;
const int MAXN = 50000;

vector<pair<int, int>> SAMPLES(MAXN);

bool compare(const pair<int, int>& p1, const pair<int, int>& p2) {
	return p1.first < p2.first;
}

struct cmp {
	bool operator()(const pair<int, int>& p1, const pair<int, int>& p2) {
		// 좌표 기준 오름차순
		return p1.second > p2.second;
	}
};

int solution() {
	int MIN_ANS = 1e9 + 1;

	// 좌표 기준 오름차순 정렬
	sort(SAMPLES.begin(), SAMPLES.begin() + N, compare);
	
	// ID 종류 카운트
	set<int> idTypeSet;
	for (int i = 0; i < N; i++) {
		if (idTypeSet.find(SAMPLES[i].second) == idTypeSet.end())
			idTypeSet.insert(SAMPLES[i].second);
	}

	int IdTypeNum = idTypeSet.size();

	map<int, int> ID_MAP;
	set<int> LOC_SET;

	for (int i = 0; i < N; i++) {
		pair<int, int> p = SAMPLES[i];
		int loc = p.first;
		int id = p.second;

		if (ID_MAP.find(id) != ID_MAP.end()) {
			LOC_SET.erase(ID_MAP[id]);
		}

		ID_MAP[id] = loc;
		LOC_SET.insert(loc);
		
		if (ID_MAP.size() == IdTypeNum) {

			MIN_ANS = min(MIN_ANS, loc - (*LOC_SET.begin()));
		}
	}

	return MIN_ANS;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int loc, id;
		cin >> loc >> id;
		SAMPLES[i] = { loc, id };
	}

	int answer = solution();
	cout << answer << endl;

	return 0;
}