문제
와 정말 정말 오래걸린 문제이다.
살짝 부끄럽지만 일단은 내가 vector, pair ,stable_sort, map ,unordered_map,find,find_if 등에 대해서 공부하는 시간이 됐다.
정답 코드
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <unordered_map>
using namespace std;
bool my_sort(pair<int,int> a,pair<int,int> b)
{
return (a.second > b.second);
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
int n,c;
cin >> n >> c;
vector<pair<int ,int >>arr;
int num;
for (int i=0;i < n;i++)
{
cin >> num;
auto a = find_if(arr.begin(),arr.end(), [&num](const pair<int, int>& elem){ return elem.first == num;});
if (i == 0 || a == arr.end())
{
arr.push_back({num,1});
}
else
a->second++;
}
stable_sort(arr.begin(),arr.end(),my_sort);
for (auto it : arr)
{
for (int i=0; i < it.second;i++)
{
cout << it.first<< " ";
}
}
}
문제 풀이의 흐름
- 풀이 흐름은 간단하다.
- pair벡터 베열에 첫번째 요소는 숫자, 두번째 요소는 그 숫자의 갯수를 의미한다.
- 만약 pair에 이 값이 있는지 확인하고 값이 존재한다면 갯수를 늘려주고, 아니라면 새롭게 1개로 푸쉬를 한다.
- 이 과정을 반복해주고 처음 들어온 순서를 보존하면서 갯수가 큰 순으로 정렬을 해주고
- 그 정렬한 값만큼 쭉 출력을 해준다.
주의 할 점
find와 find_if()
find 함수
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);와 같은데 이건 맨 마지만 val 인자의 타입 T에 ==이 정의 되어 있어야만 사용할 수 있다.
하지만 pair같은 경우 first 와 second를 비교 할 거라서 꼭 find_if()함수를 써줘야만 한다.
find_if() 함수
template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, \
UnaryPredicate pred);맨 마지막 pred 인자에 내가 원하는 조건식(bool 리턴값을 가지는)을 작성해서 넣어주면 됩니다.
pair 구조체에는 operator== 가 정의되어 있지 않아서 find를 사용하면 같은 값을 찾을 수 없습니다.
틀린코드
auto a = find(arr.begin(),arr.end(),num);수정 코드
auto a = find_if(arr.begin(),arr.end(), \
[&num](const pair<int, int>& elem){ return elem.first == num;});수정 된 코드를 보면 아에 모르는 개념이 등장하는데 [&num] 이게 뭐냐?
C++11 이상에서 람다 식(종종 람다 라고도 함)은 함수에 인수로 호출되거나 전달되는 위치에서 익명 함수 개체( 클로저 )를 정의하는 편리한 방법입니다. 일반적으로 람다는 알고리즘 또는 비동기 함수에 전달되는 몇 줄의 코드를 캡슐화하는 데 사용됩니다.
람다식
- capture 절 (C++ 사양의 람다 소개자 라고도 함)
- 매개 변수 목록 선택적. ( 람다 선언자라고도 함)
- 변경 가능한 사양 선택적.
- exception-specification 선택적.
- trailing-return-type 선택적.
- 람다 본문입니다.
Capture 절
[ ] 이렇게 빈 캡쳐절을 사용하는 건 람다 식의 본문이 바깥쪽 범위 변수에 엑세스 하지 않는 것을 의미합니다.
그리고 이 안에 넣는 변수가 [&A] 로 넣을수도 있고 [A] 이렇게 값으로 엑세스 할 수도 있다. 그 외에 이렇게도 사용이 가능한데
[&total, factor]
[factor, &total]
[&, factor]
[=, &total]
이 이상의 내용은 레퍼런스를 참고하도록 하자.
stable_sort()
stable_sort 함수는 여러 값들이 묶여 있을 때 하나의 요소로 정렬 할 때 다른 요소들의 정렬 순서도 정렬 전과 같이 유지 될 수 있도록 하는 정렬입니다.
#include <algorithm>
bool my_sort(pair<int,int> a,pair<int,int> b)
{
return (a.second > b.second);
}
stable_sort(arr.begin(),arr.end(),my_sort);사용은 sort와 비슷하게 사용이 됩니다.
또 stable_sort가 sort보다 빠르며, 유용하게 쓰일 때가 있다.
인자로 비교하는 함수에 레퍼런스 타입을 넣어주게 되면 컴파일 에러가 난다.
bool my_sort(pair<int,int> &a,pair<int,int> &b)비교 함수를 이렇게 만들었었는데 자꾸 에러가 나서 레퍼런스를 지웠더니 컴파일이 됐다.
이렇게 const를 붙혀도 된다.
bool my_sort(const pair<int,int> &a,const pair<int,int> &b)
{
return (a.second > b.second);
}이게 되는 이유는 함수의 전달인자가 반드시
bool cmp(const Type1 &a, const Type2 &b);이렇게 생겨야 하기 때문이다.
반성 및 고찰
오답코드
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <unordered_map>
using namespace std;
int my_sort(pair<int,int> &a,pair<int,int> &b)
{
return (a.second >= b.second);
}
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
int n,c;
cin >> n >> c;
unordered_map <int,int> arr;
int num;
for (int i=0;i < n;i++)
{
cin >> num;
arr[num]++;
}
vector<pair<int,int>> v(arr.begin(),arr.end());
sort(v.begin(),v.end(),my_sort);
for (auto it : v)
{
for (int i=0; i < it.second;i++)
{
cout << it.first<< " ";
}
}
}
//unordered map은 자동으로 정렬이 되지 않지만 그렇다고 입력된 순으로 값을 저장하고 있지 않다는 성질이 있어서 위의 코드가 틀렸었습니다unordered_map은 자동으로 정렬이 되지 않지만 그렇다고 입력된 순으로 값을 저장하고 있지 않다는 성질이 있어서 위의 코드가 틀렸었습니다
위 코드는 unordered_map을 정렬하는 부분도 있지만 이건 stable하지 않아서 잘 쓸일은 없을 것 같아요.
이 문제는 안 써본 것들에 대한 많은 공부가 된 문제입니다.
Uploaded by N2T