글 읽기 - 10814 stable_sort질문드립니다.

2015136077 4년 전 0

해당 코드의 입력을

21 jun

21 do

20 sun

으로 입력을 했다면

stable_sort에 의해 출력값이 일치하기에 두번째 값들은 인덱스 순서를 유지하여

20 sun

21 jun

21 do

가 출력되어야 한다 생각했습니다.

근데 sort나 stable_sort나 결과 값이

20 sun

21 do

21 jun이 나오는데 이해가 가지않습니다.

왜 둘의 결과가 차이가 없이 출력되나요.

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

using namespace std;

/*
bool cmp(pair<int, string> a, pair<int, string> b){
	if(a.first==b.first){
		return false;
	}
}*/



int main(){
	int num=0;
	scanf("%d",&num);
	vector< pair<int,string> > v;
	
	v.resize(num);
	for(int i=0;i<num;i++){
		cin>>v[i].first>>v[i].second;
	}
	
	stable_sort(v.begin(),v.end());
	
	for(int i=0;i<v.size();i++){
		printf("%d %s\n",v[i].first,v[i].second.c_str());
	}
} 

djm03178 4년 전 1

pair::operator< 자체가 first가 같으면 그 다음 second를 비교하기 때문에 {21,jun}과 {21,do}는 대소관계가 성립하는 서로 다른 값입니다. 따라서 stable이든 아니든 같은 결과를 내게 됩니다.

pair에서 stable_sort를 통해 순서가 유지되려면 second까지 같아야 합니다. (즉, 이 문제에서는 의미가 없습니다.)

2015136077 4년 전 0

pair를 통해서 문제를 해결했는데 말씀하신대로라면 제가 작성해 AC뜬 코드도 문제가 있는데 백준에서 걸러내지 못한것같네요. 감사합니다

djm03178 4년 전 1

정답을 받으신 코드는 cmp 함수를 만들어서 second를 보지 않게 만들었기 때문에 first만 같으면 같은 원소로 보고 기존의 순서를 유지하니 정답을 받는 것이 맞습니다.

2015136077 4년 전 0

감사합니다!

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

문제

문제

출처

ICPC

10814 stable_sort질문드립니다.

2015136077 4년 전 0

djm03178 4년 전 1

2015136077 4년 전 0

djm03178 4년 전 1

2015136077 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말