글 읽기 - vector sort 반례가 있나요?

sje8175 1년 전 0

stable sort 고려해서 compare 함수에서 나이 같을 경우 false를 리턴하여 가입 순서대로 나오게 구현한 것 같은데 틀렸다고 합니다.

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

bool compare(pair<int,string> p1, pair<int,string> p2) {
	if (p1.first == p2.first) return false;
	return p1.first < p2.first;
}
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int cycle;
	cin >> cycle;

	vector<pair<int,string>> arr;
	int age;
	string name;

	for (int i = 0; i < cycle; i++) {
		cin >> age >> name;
		arr.push_back(make_pair(age, name));
		
	}

	sort(arr.begin(), arr.end(), compare);

	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i].first << " " << arr[i].second << '\n';
	} 
	

	
}

ks0689 1년 전 0

저도 처음에 작성자님과 같은 방식으로 했는데, 11퍼에서 틀렸다고 나오더라고요....

stable_sort(members.begin(), members.end(), compare);
//stable_sort : 같은 원소더라도 원래의 순서가 sorting 후에도 유지되는 정렬방식

sort 키워드를 stable_sort로 바꾸시면 바로 통과됩니다.

알고리즘이 저랑 같아서 분명히 통과 되실겁니다.

ks0689 1년 전 0

지금 보니 단계별로 풀어보기 문제 설명란에도

"값이 같은 원소의 전후관계가 바뀌지 않는 정렬 알고리즘을 안정 정렬(stable sort)이라고 합니다."

라고 나와있었네요.... ㅜㅜㅜ

sje8175 1년 전 0

바꾸니 되었네요! 감사합니다ㅜㅜ

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

문제

문제

출처

ICPC

vector sort 반례가 있나요?

sje8175 1년 전 0

ks0689 1년 전 0

ks0689 1년 전 0

sje8175 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말