hkhunk0202   1년 전

문제를 풀면서 sort함수를 stable_sort함수로 변경한 것 만으로 정답 처리되어서 질문 드립니다.

저의 풀이 접근 방식은

1. 입력 순서를 seq 배열에 기록

2. 빈도 수를 unordered_map에 기록

3. sort함수를 사용해 seq 배열을 빈도 수로 추가로 정렬
결과로는 sort함수를 사용했을 때 틀렸고, stable_sort함수로만 바꿨더니 정답 처리가 되었습니다.

저의 생각은sort함수에서 조건이 참이라면 빈도 수로 정렬된다.

조건이 거짓이라면 정렬이 수행되지 않고 입력 순서가 유지된다. 라고 접근을 했습니다.

저가 생각한 sort함수의 동작이 어떤 부분에서 잘못되었는지 조언 부탁 드립니다.

keyboardmunji   1년 전

sort 와 stable sort의 차이는 stable sort가 상대적 순서가 유지된다는 것인데, 현재 seq 배열은 중복제거 기능만 합니다. 입력순서도 같지만 값이 sort시 값이 같으면 입력순서가 뒤바뀔 수 있다는 것이죠. stl sort의 특성이 quick sort만 하는게 아니라 최적화를 위해 heapsort도 써서 생각대로 안될 가능성이 높습니다. 따라서 sort할 때 상대적 순서가 유지되지 않아 WA를 받습니다.

hkhunk0202   1년 전

감사합니다.

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