안녕하세요 기린입니다 :)
이번에는 지난 시간까지 배운 정렬들을 활용하여 백준 온라인 저지 https://www.acmicpc.net/ 에 있는 심화 정렬 문제들을 풀어보고자 합니다. 실제 프로그래밍 대회나 실무에서 요구하는 대부분의 정렬 문제는 단순한 형태의 정렬 문제가 아닙니다. 다양하게 연관된 데이터 상에서 정렬을 수행해야 하는 문제가 대부분입니다. 따라서 심화적인 정렬 문제들을 풀어보면서 연습하는 시간이 필요합니다.
① 단어 정렬 https://www.acmicpc.net/problem/1181
위 문제는 단어들을 정렬하는 문제입니다.
알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.
1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로
입력: 첫 째줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.
출력: 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한번씩만 출력한다.
위 문제는 단어들을 정렬하는 문제입니다. 다만, 단순히 사전순으로 정렬하는 것이 아니라 길이가 더 짧은 것을 출력하되, 길이가 같으면 그 때 사전순으로 정렬해야 한다는 특징이 있습니다.
#include <iostream>
#include <algorithm>
using namespace std;
string a[20000];
int n;
bool compare(string a, string b) {
// If the length is shorter
if (a.length() < b.length()) {
return 1;
} else if (a.length() > b.length()) {
return 0;
}
// If the lengths are the same
else {
return a < b;
}
}
int main(void) {
// Input n
cin >> n;
// Input n variables
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// Sort
sort(a, a + n, compare);
// Output
for (int i = 0; i < n; i++) {
if (i > 0 && a[i] == a[i - 1]) {
continue;
} else {
cout << a[i] << '\n';
}
}
return 0;
}
② 시리얼 번호 https://www.acmicpc.net/problem/1431
마찬가지로 문자열을 정렬하는 것이긴 한데 조건이 더 복잡한 정렬 방식을 요구합니다.
다솜이는 기타를 많이 가지고 있다. 그리고 각각의 기타는 모두 다른 시리얼 번호를 가지고 있다. 다솜이는 기타를 빨리 찾아서 빨리 사람들에게 연주해주기 위해서 기타를 시리얼 번호 순서대로 정렬하고자 한다.
모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있다.
시리얼번호 A가 시리얼번호 B의 앞에 오는 경우는 다음과 같다.
1. A와 B의 길이가 다르면, 짧은 것이 먼저 온다.
2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교해서 작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)
3. 만약 1, 2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다. 숫자가 알파벳보다 사전순으로 작다.
시리얼이 주어졌을 때, 정렬해서 출력하는 프로그램을 작성하시오.
입력: 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어져 있다. 시리얼 번호는 중복되지 않는다.
출력: 첫째 줄부터 차례대로 N개의 줄에 한줄에 하나씩 시리얼 번호를 정렬한 결과를 출력한다.
바로 소스코드를 보시죠
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector <string> v;
int getSum(string a) {
int length = a.length(), sum = 0;
for (int i = 0; i < length; i++) {
// If a is number
if (a[i] - '0' <= 9 && a[i] - '0' >= 0) {
sum += a[i] - '0';
}
}
return sum;
}
bool compare(string a, string b) {
// If the length is shorter
if (a.length() < b.length()) {
return 1;
} else if (a.length() > b.length()) {
return 0;
}
// If the lengths are the same
else {
int aSum = getSum(a);
int bSum = getSum(b);
// If the sum of the numbers in a eltter is different
if (aSum != bSum) {
return aSum < bSum;
} else {
return a < b;
}
}
}
int main(void) {
// Input n
cin >> n;
// Input n variables
string input;
for (int i = 0; i < n; i++) {
cin >> input;
v.push_back(input);
}
// Sort
sort(v.begin(), v.end(), compare);
// Output
for (int i = 0; i < n; i++) {
cout << v[i] << endl;
}
return 0;
}
getSum 함수를 이용해 문자열 내에 숫자만 합하여 반환하고 compare 함수에서 먼저 길이 순서로 정렬하고 길이가 같으면 문자열 내 숫자가 적은 순으로 정렬하고 숫자마저 같다면 사전순으로 정렬하도록 구현합니다.
③ 수 정렬하기 3 https://www.acmicpc.net/problem/10989
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력: 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
출력: 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
시간 복잡도 O(N)을 요구하는 정렬 문제입니다. 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 힙 정렬 등 대부분의 알고리즘으로는 풀지 못합니다. 숫자의 범위가 정해져 있을 때만 매우 빠르게 계산 해낼 수 있는 정렬 알고리즘인 계수 정렬 알고리즘을 사용하면 됩니다.
#include <iostream>
using namespace std;
int n;
int a[10001];
int main(void) {
// Input n
scanf("%d", &n);
// Input n variables and counting
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
a[x]++;
}
// Output
for (int i = 0; i < 10001; i++) {
while (a[i] != 0) {
printf("%d\n", i);
a[i]--;
}
}
return 0;
}
간단한 문제이지만 기본적인 정렬 알고리즘을 사용하여 풀어야 하는 문제이니 한번 씩 고민해보시고 스스로 풀어보시면 좋을것 같습니다.
자 그럼 즐거운 코딩하세요 :)
문의: ralla0405@gmail.com
