[BOJ/C++] 단계별로 풀어보기 - 정렬(2)

2026.01.12일차입니다.
요즘은 하드 락이나 메탈보다 얼터 락을 좀 더 많이 듣는 거 같아요
오늘은 Boulevard of Broken Dreams 들으면서 코테 풀었어요
노래 자체도 좋긴한데 가사 이입해서 들으면 뭐랄까 머릿속이 정돈된다고 해야하나
아무튼 정렬 풀어보았습니다.

2587번 대표값2

문제 링크
평균과 중앙값을 구하는 문제입니다. 5개의 값을 정렬 후 중앙값인 a[2]를 출력하면 되는 간단한 문제입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a[5], t = 0; for (int i = 0; i < 5; ++i) { cin >> a[i]; t += a[i]; }
    sort(a, a + 5); cout << t / 5 << '\n' << a[2];
}

전 글에서 말했다시피 여러 문제에서 정렬 알고리즘을 구현하긴 귀찮기도 하고 실제 코테에서도 내장 함수를 사용하므로 저도 내장 함수를 사용했습니다.

커트라인

문제 링크
커트라인의 점수는 내림차순에서 k번째인 학생의 점수입니다.

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int N, k; cin >> N >> k; int* a = new int[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N); cout << a[N - k];
}

다음과 같이 오름차순 정렬 후 뒤에서 k번째 원소라고 하여도 정답입니다.

10989번 수 정렬하기 3

문제 링크
카운팅 정렬을 이용하는 문제입니다.
카운팅 정렬(Counting sort)이란 배열 내에 각각의 원소가 몇 개가 있는지 세어 원소들을 순서대로 그 개수만큼 채워 배열을 완성하는 알고리즘입니다.

카운팅 정렬을 이해하는 데에는 해당 글을 읽어보는 것을 추천드립니다.
저 또한 1~2년 전 즈음에 해당 글을 보고 공부했던 기억이 있습니다.

하지만 카운팅 정렬을 그대로 구현하게 되면 메모리 초과가 발생하여 카운팅 정렬의 일부 특성만을 이용하여 풀도록 합니다.

다음과 같은 배열이 있다면 배열 내의 원소가 각각 몇 개 있는지 카운팅 합니다.

다음과 같은 배열을 얻을 수 있고 해당 문제에서는 정렬 결과를 출력하기 만을 요구하고 있습니다.
따라서 0부터 최댓값까지 해당 배열을 순회하며 해당 요소의 개수만큼 출력하기만 하면 됩니다.

#include <iostream>
using namespace std;
int main() {
    int N, m = 0; cin >> N; int c[10001] = { 0, };
    for (int i = 0; i < N; ++i) { int t; cin >> t; ++c[t]; m = t > m ? t : m; }
    for (int i = 1; i <= m; ++i) for (int j = 0; j < c[i]; ++j) cout << i << '\n';
}

배열을 입력 받는 과정에서 동시에 최댓값을 추출합니다.
이렇게 최댓값을 얻어내면 1부터 10001까지 훑을 필요 없이 최댓값까지만 훑으면 됩니다.
i<=m이 아닌 i<10001로 적어도 정답이지만 시간은 전자가 조금 더 빠릅니다.

1427번 소트인사이드

문제 링크
각 자리수를 내림차순으로 정렬하는 문제입니다. string 문자열을 사용하면 쉽게 풀 수 있습니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
int main() {
    string N; cin >> N; sort(N.begin(), N.end(), greater<>()); cout << N;
}

sort 함수의 세 번째 인자는 입력하지 않으면 기본값은 오름차순 정렬입니다.
내림차순 정렬을 위해서는 세 번째 인자에 내림차순 정렬을 가능하게 하는 함수 포인터를 대입해주어야 합니다.
<functional> 헤더의 greater<>()를 사용하면 함수를 구현하지 않고도 쉽게 내림차순 정렬을 할 수 있습니다.
오름차순 정렬의 경우에는 less<>()를 사용합니다.

11650번 좌표 정렬하기

문제 링크
x좌표를 기준으로 오름차순, x좌표가 같다면 y좌표를 기준으로 오름차순 정렬을 진행합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int N; cin >> N; vector<pair<int, int>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end()); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

두 좌표쌍은 vector 배열의 pair을 이용하여 쉽게 정의할 수 있습니다.
첫 번째 값은 .first로 접근하며 두 번째 값은 .second를 통해 접근합니다.
sort 함수의 세 번째 인자를 설정하지 않으면 자동으로 오름차순 정렬을 진행합니다.
pair의 경우에도 .first 오름차순 > .second 오름차순으로 정렬이 이루어집니다.

11651번 좌표 정렬하기 2

문제 링크
두 번째 문제는 y좌표를 기준으로 오름차순, y좌표가 같다면 x좌표를 기준으로 오름차순 정렬을 진행합니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(pair<int, int>& v1, pair<int, int>& v2) { if (v1.second == v2.second) return v1.first < v2.first; else return v1.second < v2.second; }
int main() {
    int N; cin >> N; vector<pair<int, int>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), cmp); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

.second가 1순위가 되어야 하므로 비교 함수를 따로 작성해야 합니다.
해당 코드처럼 bool을 반환하는 cmp 함수가 그 역할을 합니다.

1181번 단어 정렬

문제 링크
해당 문제 또한 비교 함수를 작성하는 문제라 크게 어려운 것이 없습니다.
길이 오름차순 이후 사전순(오름차순) 정렬을 진행합니다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(string s1, string s2) { if (s1.length() == s2.length()) return s1 < s2; else return s1.length() < s2.length(); }
int main() {
    int N; cin >> N; string* a = new string[N]; for (int i = 0; i < N; ++i) cin >> a[i];
    sort(a, a + N, cmp); 
    for (int i = 0; i < N; ++i) if (i == 0 || a[i] != a[i - 1]) cout << a[i] << '\n';
}

10814번 나이순 정렬

문제 링크
나이를 기준으로 정렬하되, 나이가 같다면 입력 순서는 유지되어야 합니다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
bool cmp(pair<int, string>p1, pair<int, string>p2) { return p1.first < p2.first; }
int main() {
    int N; cin >> N; vector<pair<int, string>> v(N); for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;
    stable_sort(v.begin(), v.end(), cmp); for (int i = 0; i < N; ++i) cout << v[i].first << ' ' << v[i].second << '\n';
}

따라서 stable_sort 함수를 사용해야 합니다.
해당 함수는 이름 그대로 안정 정렬을 수행합니다.
그냥 sort를 사용할 경우 오답처리 됩니다.

18870번 좌표 압축

문제 링크
해당 원소보다 서로 다른 작은 원소가 몇 개 있는지를 출력하는 문제입니다.

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;
int main() {
    int N; cin >> N; vector<long long> v1(N); vector<long long> v2(N); for (int i = 0; i < N; ++i) { cin >> v1[i]; v2[i] = v1[i]; }
    sort(v2.begin(), v2.end()); v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (int i = 0; i < N; ++i) cout << lower_bound(v2.begin(), v2.end(), v1[i]) - v2.begin() << ' ';
}

사용해야 할 함수가 많아 조금 당황했던 문제입니다.
unique 함수는 <algorithm> 헤더 내에 존재하며 중복되는 원소들을 뒤로 밀어낸 뒤 중복되지 않은 데이터들이 끝나는 지점을 반환합니다.
erase 함수는 지정 범위를 삭제하는 함수입니다.
따라서 중복되는 부분을 모두 삭제합니다.
lower_bound 함수는 해당 원소가 범위 내에서 처음 등장하는 위치를 찾습니다.
해당 위치에서 배열의 시작 부분을 빼면 해당 원소의 인덱스, 즉 해당 원소 앞에 있는 원소의 개수가 됩니다.