2-G 문제 풀이 질문있습니다

작성한 질문수 5

0

안녕하세요 규현님 ㅎㅎ

해당 코드에서 수정할게 있는데요.

bool cmp(ll x, ll y){
	if(mp[x] > mp[y]) return 1;
	else if (mp[x] < mp[y]) return 0;
	else{
		if(find(begin(a), begin(a)+n, x) <= find(begin(a), begin(a)+n, y)) return 1;
		else return 0;
	}
}

이부분이요. find를 통해서 해당 이터레이터를 기반으로 대소비교를 하고 있죠?

이렇게 하시면 안됩니다. 원하는 로직은 예를 들어 1, 1, 2, 2, 2 일 때 0과 2를 비교해서 더 작은 거가 앞으로 오게

이런게 아닐까요?

근데 이터레이터 즉, 주소값을 중심으로 대소비교를 하게 되면 UB가 발생되게 됩니다. 물론 메모리에 순차적으로 쌓여서 어느정도 순서가 유지가 될 수도 있지만 항상 UB는 주의해야 하거든요.

그래서 이런식으로 begin을 빼주는게 첫번째 중요한 점입니다.

bool cmp(ll x, ll y){
	if(mp[x] == mp[y]){
		int pos1 = find(begin(a), begin(a)+n, x) - begin(a);
		int pos2 = find(begin(a), begin(a)+n, y) - begin(a);
		return pos1 < pos2;
	}
	return mp[x] > mp[y]; 
}

근데, 사실

이 코드는 틀린 코드입니다.

sort는 어떤 것을 정렬하죠? a라는 배열을 정렬하게 됩니다. 근데 sort안에 들어가는 cmp라는 함수는

a라는 배열을 참조해서 로직이 구성이 되죠? 그렇기 때문에 UB가 발생하게 됩니다.

sort는 배열안에 있는 각각의 요소들을 서로 비교해가며 일어나게 됩니다. 근데 이 중간 중간에 a를 참조하게 되면 원본 배열을 중심으로 find를 하려고 했던 규현님의 로직과는 동떨어진 로직이 발생되게 됩니다.

그래서 틀린 거 같습니다.

UB는 unexpected behavior를 의미합니다.

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

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

감사합니다.

강사 큰돌 올림.