백준 13414 c++

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

13414번: 수강신청

 

입력제한이  K(1 ≤ K ≤ 100,000) , L(1 ≤ L ≤ 500,000) 인것을 봤을때부터 시간복잡도 오류를 발생하게 하려는 문제인걸 짐작했다.

내가 현재 아는 수준으로는 2중 for문을 이용해 이미 등록된 아이디인지 하나씩 검색하는 방법밖에 몰라서 구글링을 한뒤 map 자료형에 대해 알게되었다.

map은 파이썬의 dictionary와 비슷하게 key값과 value값으로 이루어져 있으며 이미 map 안에 저장된 key 값이 있을경우 value 값만 갱신해주는 형태이다

 

map을 이용해서 이미 저장된 key일 경우 value 값을 가장 나중으로 바꿔주는 식으로 l번만큼 반복문을 실행 한뒤 pair<string,int> 로 된 벡터를 이용해 값을 하나씩 집어 넣어준다.

그 후 두번째 인자를 기준으로 sort 하면 우선 순위가 나오게된다

#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

bool compare(const pair<string,int>& a, const pair<string,int>& b)
{
	return a.second < b.second;
}

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

	int n,m;
	cin >> n >> m;
	unordered_map<string, int> v;
	vector<pair<string,int>> lee;
	for(int i=0; i<m; i++) {
		string str;
		cin >> str;
		v[str] = i;
	}
	
	for(auto &i : v) {
		lee.push_back(i);
	}
	
	sort(lee.begin(),lee.end(),compare);
	
	for(int i=0; i<n; i++) {
		cout << lee[i].first << endl;
	}
	return 0;
}