[99클럽 코테 스터디 27일차 TIL] #정렬2

27일 차입니다. 오늘은 술약속이 있어서 그전에 잠깐 공부하러 카페에 왔어요. 타르트 맛집이라는데 타르트 한 개에 9000원이어서 식겁했네요 ㅎㄷㄷ
그래도 맛있으니까 참겠습니다 ^^; 맛있는 것도 잘 먹었으니 공부도 열심히 해보겠습니다~
 

문제 설명

---

 
술약속있는 날에 술과 관련된 문제가 나와서 놀랐네요. 이런 우연이 ㅇ..
이 문제는 각 학교별 술 소비량이 주어지고 학교들 중 술소비량이 가장 많은 학교의 이름을 출력하는 단순한 문제였습니다.
https://www.acmicpc.net/problem/11557
 
 

생각 흐름

---

우선 학교와 술소비량이 주어지고 이들의 대소비교를 하는 문제였기 때문에 두 개의 변수를 저장하며 요소 접근이 쉬운 자료구조들을 떠올려보았습니다.
 
음.. vector, map 등이 생각이 났는데 map이라는 자료구조가 key, value 값을 가지고 대소비교를 하기 쉽다고 생각하여 무작정 map을 써야겠다고 생각했습니다.
 
앞에서부터 차근차근 테스트 개수 t를 받아오도록 하고 반복문을 돌려 학교 수 n을 우선 받도록 코드를 작성했습니다.
 
그리고 변수들을 저장할 map 자료구조를 map <string, int> m; 이런 식으로 선언을 하였고 string 변수인 school과 int형 변수 drink를 차례대로 받아주어 map에 저장해 주었습니다.
 
이제 정렬을 해주면 되는데, 생각을 해보니 map은 value를 기준으로 정렬을 하지 못한다는 점이었습니다.
 
key를 기준으로 자동 정렬이 되는 자료구조인데 value를 정렬할 수는 없을까? 고민하다가 구글링을 해보았습니다. 역시 개발자는 구글링이죠.
 
map 같은 경우 key를 기준으로 자동으로 오름차순 정렬이 되지만 이를 value 값을 기준으로 정렬을 하려면,
vector를 pair로 새로 선언을 해서 map의 요소들을 넣어준 뒤, 이를 사용자 비교함수를 이용해 따로 정렬해 주면 되는 것이었습니다.
 
우선 블로그에 있던 코드를 따라 적어보기로 했습니다.
 
우리에게 필요한 것은 value 값을 기준으로 내림차순 정렬, (가장 큰 값이 제일 앞에 오게 하는 것)이었기 때문에 사용자 함수를 따로 정의해 준 것이었습니다.

bool compare (const pair <string, int> &a, const pair <string, int> &b) { // map의 value값을 정렬해주기 위한 compare 함수
    if (a.second == b.second) { // value 값이 같다면
        return a.first > b.first; // key값이 큰 것
    }
    return a.second > b.second; // value 값이 더 큰 것 출력
}

 
pair형 vector 요소 a, b가 주어지면 a와 b의 value 값을 비교해서 더 큰 값을 return 하는 것입니다.
 
또한 이를 사용하기 위해 vector 자료구조를 따로 선언해 주었는데

vector <pair <string, int>> v (m.begin(), m.end()); // value 기준 정렬을 해주기 위해 벡터선언 v

 
m에 있는 요소를 그대로 넣어주어 vector 자료구조를 새로 정의해 주었고 sort 함수를 이용해 정렬까지 해주었습니다.
 
그런 다음 제일 첫 번째 요소의 first를 출력해 주어 마무리하였습니다.
 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int t, n; // 테스트 케이스 숫자 t, 학교의 숫자 정수 n
string school; int drink; // 학교 이름과 술량을 저장할 변수 

bool compare (const pair <string, int> &a, const pair <string, int> &b) { // map의 value값을 정렬해주기 위한 compare 함수
    if (a.second == b.second) { // value 값이 같다면
        return a.first > b.first; // key값이 큰 것
    }
    return a.second > b.second; // value 값이 더 큰 것 출력
}

int main () {
    cin >> t; // 테스트 케이스 수 t를 받아옴

    map <string, int> m; // 술 소비량과 학교를 저장할 map 선언

    for (int i = 0; i < t; i++) {
        cin >> n; // 학교 수를 받아옴 n
        for (int j = 0; j < n; j++) {
            cin >> school >> drink;
            m[school] = drink; // 각 학교마다 술 소비량 저장
        }

        vector <pair <string, int>> v (m.begin(), m.end()); // value 기준 정렬을 해주기 위해 벡터선언 v
        // map은 따로 정렬함수가 없어서 벡터에 넣어서 정렬해줄 것임
        sort (v.begin(), v.end(), compare); // compare 함수를 이용해 value 값 정렬
        // 내림차순 정렬이 되어있기 때문에 첫번째 요소의 first 값을 출력하면 됨..

        cout << v.begin()->first << "\n";  

        m.clear(); // m 다시 비워줌
        v.clear(); // v 다시 비워줌
    }
    
    return 0;
}

 
 
아! 그리고 각 테스트 케이스마다 map, vector를 초기화해 주어 새로 요소를 받아오도록 하였습니다.
 
 

공부한 내용 정리

---

오늘 문제를 풀면서 핵심포인트였던 value 값을 기준으로 map 정렬하기를 자세히 찾아보려고 합니다.
다음에도 이런 문제가 나오면 바로 생각이 날 수 있게 꼼꼼히 공부해 보겠습니다.
 

1. map 정렬

map 자료구조는 기본적으로 key 값을 기준으로 한 오름차순 기반 정렬을 하고 있습니다. 
기본구조는 다음과 같다고 합니다.
 

template < class Key,                                     // map::key_type
           class T,                                       // map::mapped_type
           class Compare = less<Key>,                     // map::key_compare
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type
           > class map;

 
자세히는 모르겠으나 key 값을 기준으로 오름차순 정렬을 하는구나~를 알 수 있는 코드였습니다.

---

 
근데 난 key 값 기준 내림차순으로 정렬을 하고 싶다 하면 3번째 인자에 greater <>을 넣어주면 됩니다.

// 키, 데이터, compare
map<int, string, greater<int>> m;

 
key값이 아니라 value 값을 기준으로 정렬하기 위해서는 어떻게 해줘야 할까요?
 

2. value 값 기준 map 정렬

map에는 정렬 함수가 따로 없어서, vector를 활용해야 합니다.
구체적으로 map은 tree 형태로 되어있고, tree 형태를 만드는 과정에서 key 값을 기준으로 정렬을 합니다.
 
완성된 구조라서 따로 value값 정렬을 지원하지 않는 것으로 보입니다.
 

 
위의 그림과 같이, pair 기반의 vector에 map이 가지고 있는 pair를 모두 넣고 정렬을 하면 value값 기준 정렬이 가능해지는 것을 볼 수 있습니다.
 
(1) value 비교 사용자 정의 타입 선언
 
위에서 말했다시피 value 값을 비교해 정렬해 주려면 따로 사용자 정의 함수를 선언해주어야 합니다.

bool compare (const pair <string, int> &a, const pair <string, int> &b) {
	return a.second > b.second;
}

 
위의 코드와 같이, pair를 인자로 전달받아 두 번째 값을 비교하는 사용자 정의 함수를 작성해 줍니다.
 
(2) pair vector에 넣고 value 기준 정렬

vector <pair <string, int>> v (m.begin(), m.end());
sort (v.begin(), v.end(), compare);

 
위의 코드와 같이, m의 요소들을 pair vector에 넣어주고 사용자 정의 함수 compare을 이용한 sort 함수를 이용하면 value 값을 기준으로 정렬된 vector을 얻을 수 있습니다.
 

value값을 기준으로 map을 정렬하려면
pair vector로 따로 선언해 주어 이를 사용자 정의 비교함수를 통해 정렬해 준다

 
 
 
참고:
https://0 xd00d00.github.io/2021/08/22/map_value_reverse.html

[C++] std::map을 value 기준으로 정렬하기 - 널두