백준, C++) 2587, 25305, 2751, 10989, 1427, 11650, 11651, 1181

2587

https://www.acmicpc.net/problem/2587

void p2587()

{

    /*

     입력

     - 5개의 자연수

     출력

     - 첫 번째 줄: 평균

     - 두 번째 줄: 중앙 값

    */

    int avg = 0;

    vector<unsigned int> nums;

    for (int i = 0; i < 5; i++)

    {

        unsigned int tmp = 1;

        cin >> tmp;

        avg += tmp;

        nums.push_back(tmp);

    }

    avg /= 5;

    sort(nums.begin(), nums.end());

    cout << avg << "\n";

    cout << nums[2];

}

---

25305

https://www.acmicpc.net/problem/25305

void p25305()

{

    /*

    입력 : N (1<= N <= 1,000)

       k: 상 받는 사람

       x: 점수들

    */

    int N, k;

    vector<unsigned int> scores;

    cin >> N >> k;

    for (int i = 0; i < N; i++)

    {

        int tmp = 0;

        cin >> tmp;

        scores.push_back(tmp);

    }

    sort(scores.begin(), scores.end());

    cout << scores[N - (k - 1) - 1];

}

---

2751

https://www.acmicpc.net/problem/2751

void p2751()

{

    // 입력

    // 1 <= N <= 10^7 -> 시간 복잡도 고려

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int N;

    cin >> N;

    vector<int> a(N);

    for (int i = 0; i < N; ++i)

        cin >> a[i];

    sort(a.begin(), a.end());

    for (int i = 0; i < N; i++)

    {

        cout << a[i] << "\n";

    }

}

---

10989

https://www.acmicpc.net/problem/10989

void p10989()

{

    // counting sort로 정렬을 해야 메모리 초과가 나지 않음.

    // 입력받는 수는 많지만, 그 숫자의 크기는 작음.

    //

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int N;

    cin >> N;

    // 값의 범위가 1..10000이므로 10001 크기의 카운트 배열

    static int cnt[10001] = {0};

    for (int i = 0; i < N; ++i) {

        int x;

        cin >> x;

        ++cnt[x];   // 입력 받은 숫자: index, data는 그 숫자의 갯수

    }

    // 출력: 각 값 i를 cnt[i]번 출력

    for (int i = 1; i <= 10000; ++i) {

        while (cnt[i]--) {

            cout << i << '\n';   // 숫자가 나온 만큼 출력해주면 자동적으로 정렬이 됨.

        }

    }

}

---

1427

https://www.acmicpc.net/problem/1427

 

일반적인 정렬로 풀 경우, 메모리 초과가 발생 -> Counting sort를 이용해 메모리 사용을 줄임

void p1427()

{

    // Use Insertion sort

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int x;

    cin >> x;

    string num  = to_string(x);

    for(int i=1; i<num.size(); ++i)

    {

        int key = num[i];

        int j = i-1;

        while(j>=0 && num[j] <key)

        {

            num[j+1] = num[j];

            --j;

        }

        num[j+1] = key;

    }

    for(auto it : num) cout << it;

}

 

---

11650

https://www.acmicpc.net/problem/11650

void p11650()

{

    /*

    x,y 서로 증가하는 순으로

    */

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin >> n;

    vector<pair<int, int>> pos(n);

    for (int i = 0; i < n; ++i)

    {

        int x, y;

        cin >> x >> y;

        pos[i] = {x, y};

    }

    sort(pos.begin(), pos.end()); // x가 증가하는 순서

    for (auto it : pos)

    {

        cout << it.first << " " << it.second << "\n";

    }

}

---

11651

https://www.acmicpc.net/problem/11651

&를 사용해 원본을 swap, &를 붙이지 않고 swap하게 될 경우 복사본이 swap되어 출력이 제대로 안됨.

void p11651()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin >> n;

    vector<pair<int, int>> pos(n);

    for (int i = 0; i < n; ++i)

    {

        int x, y;

        cin >> x >> y;

        pos[i] = {x, y};    // 방법 2

                                  // y,x로 저장한 후, sort를 사용해 정렬한 다음 출력 시, it.second, it.first를 해줘도 결과는 같음.

    }

    for (auto &it : pos)  

    {

        swap(it.first, it.second);   // 스왑이 안됐음.

    }

    sort(pos.begin(),pos.end());

    for(auto &it: pos)

    {

        cout << it.second << " " <<it.first << '\n';

    }

}

---

1181

https://www.acmicpc.net/problem/1181

1. map을 사용해서 중복된 단어 제거 + 알파벳 순으로 정렬 => map 자료구조는 자동적으로 키를 정렬함.

2. vector에 pair 형태로 저장

3. sort로 길이 정렬 후, 출력

void p1181()

{

/*

정렬

- 길이가 짧은 순

- 길이 동일 -> 알파벳 순(사전 순)

*/

    int n;

    cin >> n;

    map<string, int> words;

    for(int i=0; i<n; ++i)

    {

        string s;

        cin >> s;

        words.emplace(s, s.size());

    }

   

    vector<pair<int,string>> a;

    for(auto &it : words)

    {

        a.push_back({it.second, it.first});

    }

    sort(a.begin(),a.end());

    for(auto &it : a)

    {

        cout << it.second << "\n";

    }

}

더 깔끔한 풀이

- sort안에 람다 함수를 통해 길이 순으로 먼저 정렬

- 정렬되면, 같은 문자는 서로 인접해서 정렬됨.

- v.erase(unique(v.begin(),v.end(),v.end)를 통해 중복 원소들을 끝으로 몰고, 삭제

void p1181ClearVer()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr);

    int n;

    cin >> n;

    vector<string> v;

    v.reserve(n);

    for (int i = 0; i < n; ++i) {

        string s;

        cin >> s;

        v.push_back(s);

    }

    // 길이 → 사전순

    sort(v.begin(), v.end(), [](const string& a, const string& b){

        if (a.size() != b.size()) return a.size() < b.size();

        return a < b;

    });

    // 중복 제거 (정렬되어 있으니 인접 중복만 지우면 됨)

    v.erase(unique(v.begin(), v.end()), v.end());

    for (auto& s : v) cout << s << '\n';

}