코테 준비 알고리즘 - 정렬

코테에서든, 자료구조에서든 정렬은 항상 빼놓지 않고 등장하는 중요 요소입니다.

또한 많은 알고리즘의 기본 base로 깔고 가는 개념이기도 하죠. 자료구조 수업에서도 정렬을 구현하는 수많은 방법을 배우고, 그 방법을 익히는 것도 중요하지만, 이 글에서는 정렬 방법에 대해서는 다루지 않습니다.

이번 포스트에서는 정렬 개념을 어떤 방식으로 문제에 적용시키는지, c++에서는 어떻게 정렬하는지 정도를 설명해 드리겠습니다.

---

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

---

단순히 정렬만 하는 문제입니다. 문제의 의도는 다양한 정렬방법을 구현해보는 것이지만, 우리는 라이브러리에서 어떻게 정렬 함수를 꺼내 쓰는지부터 알아봅시다.

	int n;
	int arr[1000000];

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

	sort(arr, arr + n);

	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}

(<algorithm> 헤더를 포함시켜야 합니다.)

int arr [] 방식처럼 배열을 선언해두었다면 다음과 같이 sort함수를 쓸 수 있습니다. 내장된 sort함수는 O(NlogN)이기에 무난히 문제를 풀 수 있죠.

만약, arr []이 아닌 vector로 배열을 만드셨다면

	int n;
	vector<int>arr;

	scanf("%d", &n);
	arr.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}

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

	for (int i = 0; i < n; i++) {
		printf("%d\n", arr[i]);
	}

다음과 같이 정렬을 할 수 있습니다.

JAVA에서도 Arrays.sort()로 정렬을 할 수 있습니다. 코드는 생략하겠습니다.

---

www.acmicpc.net/problem/1181

1181번: 단어 정렬

문제

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다.

---

이번에는 그냥 정렬만 하는 것이 아니라, 무슨 이상한 조건이 붙습니다. 이렇듯 정렬에 조건이 붙을 때 푸는 방식이 2가지로 나뉘는데, 조건이 2개라면 pair을 쓰고, 조건이 3개 이상으로 많아진다면 구조체나 클래스를 사용하는 방식이 보편적입니다.

이 문제는 조건이 2개이므로 pair을 써서 풀어봅시다. 혹시 pair에 대한 문법을 잘 모르시는 분은 

blockdmask.tistory.com/64

[C++] Pair 클래스 정리 및 예제 (vector, sort)

를 참고하시길 바랍니다. 이 블로그를 보고 오시면 아시겠지만, pair의 정렬에서는,

정렬 함수가 pair <int, int> a , pair <int, int> b를 비교할 때 a.first, b.first를 비교해 정렬하고, 만약 이 두 수가 같다면
a.second와 b.second를 비교한다.

이 것을 기억하셔야 합니다. 마침 두 조건을 비교하는 것이 문제에 그대로 적용시킬 수 있을 것 같습니다.

길이가 짧은 순으로 정렬. 하지만, 두 수가 같다면 문자열 사전 정의대로 정렬.

=> pair <>의 first는 길이 정보를 입력, second는 문자열을 입력.

 

참, 문자열 사전 정의대로 정렬은 거창한 것이 아니고 vector<string>을 정렬하면 문자열 사전정의대로 정렬한다는 의미입니다. 따라서 second의 문자열만 넣어도 first가 같다면 문자열 사전정의대로 정렬이 되겠죠.

이제 그대로 코드만 짜면 됩니다. 

	vector <pair<int, string>> v(n);
	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;
		v[i].first = s.size();
		v[i].second = s;
	}

이제 정렬하고 문제가 요구한 대로 출력만 하면 되겠죠?

JAVA에서는 pair처럼 편리하게 쓰기가 어렵고, 후에 서술하는 것처럼 compare메서드를 재정의하여 사용해야 합니다.

---

www.acmicpc.net/problem/10825

10825번: 국영수

문제

도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오.

1. 국어 점수가 감소하는 순서로
2. 국어 점수가 같으면 영어 점수가 증가하는 순서로
3. 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로
4. 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단, 아스키코드에서 대문자는 소문자보다 작으므로 사전 순으로 앞에 온다.)

입력

첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다.

출력

문제에 나와있는 정렬 기준으로 정렬한 후 첫째 줄부터 N개의 줄에 걸쳐 각 학생의 이름을 출력한다.

 

---

이번에는 정렬 조건이 4개나 됩니다. 물론 이전 문제처럼 pair을 써도 되지만, 조건이 4개므로

vector <pair <pair <int, int>, pair <int, int>>> arr

로 무지성 pair 폭격으로 코드를 적을 수도 있지만, 훨씬 더 깔끔한 방법인 구조체를 선언하여 풀어 봅시다.

struct Student
{
	string name;
	int K, E, M;
	Student(string s, int a, int b, int c) { name = s, K = a, E = b, M = c; };
	Student() { ; };
};
bool compare(Student& s1, Student& s2)
{
	if (s1.K != s2.K)
		return s1.K > s2.K;
	else
	{
		if (s1.E != s2.E)
			return s1.E < s2.E;
		else
		{
			if (s1.M != s2.M)
				return s1.M > s2.M;
			else
			{
				return s1.name < s2.name;
			}
		}
	}
}

Student 구조체를 선언하고, 학생들의 이름과 과목 성적을 멤버 변수로 둡시다.

compare 함수는 sort함수 안에 넣을 '정렬 가이드'라고 생각하시면 편합니다.

그냥 구조체를 sort함수 안에 넣고 돌리라고 하면 sort함수가 혼란에 빠지겠죠. 난 이걸 어떻게 정렬해야 할지 모르는데...

이를 위해 우리가 구조체의 정렬 가이드를 작성해 주어야 합니다. 구조체 변수 s1, s2의 우선순위를 정해 주는 작업이죠.

기본적으로 가장 우선순위가 높은 변수를 비교해 같지 않으면 변수를 비교해 반환하고, 같으면 그다음 우선순위를 비교하고, 그다음, 그다음... 

마지막으로 결정해야 할 것은 return a <b 인지, return a>b일지 부등호를 정하는 작업입니다. 외우지말고 직관적으로 생각해 봅시다.

a<b : 기준이 오름차순으로 정렬하는 것 일 때

a> b : 기준이 내림차순으로 정렬하는 것 일 때

위의 문제에서는 가장 큰 우선순위인 국어 점수가 다르다면 내림차순으로 정렬이기에 S1.K> s2.K를 return 합니다.

그다음 우선순위인 영어점수가 다르다면 오름차순으로 정렬이기에 S1.E <S2.E를 return 합니다. 어렵지 않죠?

---

이 코드를 직접 써보면서 구조체와 구조체 변수의 정렬에 대한 감을 익혀보시길 바랍니다. 이 정도의 문법만 안다면 정렬에 대해 더 들어갈 것은 없습니다. 나머지의 문제들은 대부분 정렬을 이용한 응용이 대부분이니까요.