글 읽기 - 같으면 먼저 등장한다는 조건에 대해서요

kim031504 4년 전 0

map을 이용하여 빈도수 정렬은 구현하였지만,

같은 빈도수의 경우

먼저 등장한 것부터 출력하는 것을

여기서 도대체 어떻게 구현해야 하는지 도저히 감이 안 잡혀 질문드립니다 ㅠㅠ

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

using namespace std;

bool com(const pair<int, int> &p1, const pair<int, int> &p2)
{
	if (p1.second > p2.second)
	{
		return true;
	}
	else if (p1.second == p2.second)
	{
		return false;
	}
	else
	{
		return false;
	}
	
}

int main()
{
	map<int, int> m;
	vector<pair<int, int>> v;
	
	int N, C;

	cin >> N >> C;

	


	for (int i = 0; i < N; i++)
	{
		int n;
		cin >> n;

		// 해당 키를 못 찾았다면
		if (m.find(n) == m.end())
		{
			m[n] = 1;
		}
		// 해당 키를 찾았다면
		else
		{
			// 빈도 증가!
			m.find(n)->second += 1;
		}
	}

	// map 변수 m에 값이다 담겼을 것이다.
	// 이를 pair를 이용하여 벡터에 담자.

	copy(m.begin(), m.end(), back_inserter(v));

	sort(v.begin(), v.end(), com);

	int len = v.size();

	for (int i = 0; i < len; i++)
	{
		for (int j = 0; j < v[i].second; j++)
		{
			cout << v[i].first << ' ';
		}
	}

	cout << endl;

	return 0;


}

sait2000 4년 전 1

각 수가 처음 들어오는 위치도 저장해놓고 정렬할 때 고려하면 되죠.

kim031504 4년 전 0

구조체로 묶어서 변수 하나를 추가해서 풀었습니다! 감사합니다!

jungyh0218 4년 전 0

sort할 때 key로 입력 순서를 하나 더 정하셔도 좋고,

stdlib 의 sort 는 정렬 시 순서가 지켜짐을 보장하지 않습니다. (unstable sort) 만약 원소 개수가 그다지 많지 않고, 시간이 널널하게 주어졌다면 stl에서 제공하는 stable_sort를 사용하는 것도 고려해보실 수 있을 듯... 대부분의 경우 sort보다 성능이 쳐지기는 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

같으면 먼저 등장한다는 조건에 대해서요

kim031504 4년 전 0

sait2000 4년 전 1

kim031504 4년 전 0

jungyh0218 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말