[백준 BOJ/C++] 1431 시리얼 번호

1431번: 시리얼 번호

 

문자열 내에서 각 문자의 정렬이 아니라 문자열들을 정렬하는 문제다.
별도의 정렬 기준이 주어지기 때문에 문자열들 간의 비교와 정렬을 연습하기 좋은 문제다.

 

일반적인 정수나 문자들 사이에서의 정렬 문제는 간단하지만 문자열들의 순서를 바꾸는 문제는 직접 경험하지 않은 상태로 만나게 된다면 헷갈릴 수 있는 부분이 있어 풀어보는 것이 좋다.

사용하는 언어의 문자열 혹은 정렬 알고리즘 라이브러리에 어느정도 익숙해야 문자열 기준의 정렬을 어렵지 않게 할 수 있다.

 

 

사용 언어에 따라 난이도 차이가 발생할 수 있으며 특히 C언어를 사용한다면 문자열 포인터와 관련해서 신경써야할 부분이 꽤 있으므로 차라리 vector를 제공하는 C++을 이용해서 쉽게 접근하는 것이 이득일 수 있다.

 

 

---

 

 

문제의 포인트

 

문자열의 배열을 정렬할수 있는가?
정렬 기준을 customize할 수 있는가?

 

 

문자열의 배열을 정렬할 수 있는가?

 

기본적으로 C 계열 언어에서 문자열은 char 형 배열이며 따라서 문자열들의 배열은 char형 2차원 배열로 표현할 수 있다.

하지만 자료구조를 이렇게 사용할 경우 각 문자열의 순서를 바꾸기 위해 문자열 간 복사가 필요해 오버헤드가 커진다.

순수하게 기본 자료형을 이용해서 풀이하고자 한다면 문자열을 가리킬 수 있는 포인터들의 배열로 접근해야 한다.

 

 

하지만 C++, Java, Python 등의 언어를 이용하면 이런 작업을 큰 어려움 없이 라이브러리를 이용해 해결할 수 있다.

C++에서는 대표적으로 string과 vector를 이용 간단히 자유자재로 순서를 바꾸거나 삽입, 제거할 수 있는 문자열의 배열 개념의 자료구조를 사용할 수 있다.

 

 

algorithm 라이브러리에서 제공하는 기본 정렬 함수에서 vector<string> 자료구조를 정렬시키는 것 역시 가능하다.

이 방법만 익숙하다면 큰 고민 없이 이와 같은 문자열들의 정렬 문제를 풀어나갈 수 있다.

 

 

vector<string> S;
sort(S.begin(), S.end());

 

 

정렬 기준을 customize할 수 있는가?

 

C언어의 stdlib.h에서 제공하는 qsort나 C++의 algorithm의 sort 함수도 기본적으로 새로 정의한 비교함수를 이용해서 정렬 기준을 재정의 할 수 있다.

새로 정의한 비교함수에서는 여러가지 기준을 순서대로 비교하면서 정렬하도록 하는 것도 가능하다.

 

 

별도의 비교함수를 정의하고 sort 함수의 함수 포인터 인자로 함수 이름을 넣어주면 정렬 시 해당 함수를 이용하는 형태이다.

대부분 언어에서 제공하는 sorting 함수들이 유사하게 이러한 비교 함수 사용을 지원한다.

 

 

이 문제는 문자열의 배열을 정렬시키되 특별한 3가지 기준으로 정렬만 시켜주고 크기나 범위 등의 실수만 조심하면 어렵지 않게 풀 수 있다.

 

 

---

 

전제 Code

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
vector<string> S;

void printS() {
	int i;

	for (i = 0; i < N; i++) {
		cout << S[i] << "\n";
	}
}

int comp(string a, string b) {
	int i, a_num = 0, b_num = 0;
	if (a.length() == b.length()) {
		for (i = 0; i < a.size(); i++) {
			if (a[i] >= '0' && a[i] <= '9')
				a_num += a[i] - '0';
		}

		for (i = 0; i < b.size(); i++) {
			if (b[i] >= '0' && b[i] <= '9')
				b_num += b[i] - '0';
		}
		
		if (a_num != b_num) {
			return a_num < b_num;
		}
		else {
			for (i = 0; i < a.length(); i++) {
				if (a[i] == b[i]) continue;
				else
					return a[i] < b[i];
			}
		}
	}
	return a.length() < b.length();
}

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i;
	string temp;

	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> temp;
		S.push_back(temp);
	}

	sort(S.begin(), S.end(), comp);
	printS();

	return 0;
}