안녕하세요 선생님! 2-G 반례를 찾기가 힘들어 질문드립니다.

작성한 질문수 1

1

안녕하세요 6030님 ㅎㅎ

지금 이 코드를 보면요.

제생각에 수강생님께서

map은 자체적으로 자동정렬이 되고

unordere_map은 정렬이 되지 않고 "들어오는 순서가 유지 된다!" 것처럼 이해하셔서

int n, c;
unordered_map<int, int> mp;

앞의 코드와 같이 unordere_map을 써서 들어오는 순서를 기반으로 vector를 만들어 정렬하는 코드를 만든거 같은데요.

unordere_map은 들어오는 순서대로도 순서가 정렬되지 않습니다. 순서를 보장하지 않은 자료구조입니다.

그렇기 때문에 UB가 떠서 틀렸다고 나오는 것 같습니다.

또한,

이 코드요.

bool cmp(pair<int, int>& a, pair<int, int>& b){
    if(a.second == b.second) return true;
    return a.second > b.second;
} 

저 true가 의미하는 것은 A와 B를 비교해서 A와 B가 같다면 A가 B 앞으로 가게 되어있고 만약 같다면 a, b를 그대로 둔다 이런 코드겠죠?

자 테스팅을 해볼까요? 수강생님은 아마 들어온 순서 그대로 내버려 두려고 한거 같은데요.

#include<bits/stdc++.h>
using namespace std;

int n, c; 

bool cmp(pair<int, int>& a, pair<int, int>& b){
    if(a.second == b.second) return true;
    return a.second > b.second;
} 
bool cmp2(pair<int, int>& a, pair<int, int>& b){
    return a.second > b.second;
} 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    vector<pair<int, int>> v = 
    {
    	{3, 2
		},
    	{1, 2
		},
		{2, 2
		}
	};
    sort(v.begin(), v.end(), cmp);
    
    for(auto it: v){ 
    cout << it.first << " : " << it.second << '\n';
    }

    return 0;
}
/*
2 : 2
1 : 2
3 : 2
*/

지금 보시면 반대로 정렬되는 것을 볼 수 있습니다.

잠시 sort의 명세서를 볼까요?

Equivalent elements are not guaranteed to keep their original relative order (see stable_sort).

앞의 말은 같은 요소에 대해서 들어온 순서 자체를 보장할 수 없는 것이죠. 즉, 들어오는 순서를 보장하려면 해당 cmp에 "들어온 순서를 담아둔 다른 자료구조"를 써야한다는 점을 알려주는 말입니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

앗.. 맞아요! 강사님께서 말씀하신게 단순하게 unordered_map을 사용하게 되면 '정렬되지 않는다' = '순서가 보장된다' 라고 생각했었습니다. 그리고 sort도 저런 특성을 갖고 있는지 전혀 파악하지 못했었네요..!

친절하고 자세하게 설명해주신 덕분에 이해됐습니다!!

아직 갈길이 너무 멀군요 :(

그래도 답변 너무 감사드립니다!!! 충분히 이해했습니다!.