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

1. 문제이해

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

1431번: 시리얼 번호

 

다솜이가 가진 기타의 갯수(N)와 각 기타들의 시리얼 번호가 주어진다.

모든 시리얼 번호는 알파벳 대문자 (A-Z)와 숫자 (0-9)로 이루어져 있을때,

아래와 같은 규칙에 따라 시리얼 번호를 정렬하는 것이 목표이다.

 

1. A, B의 길이가 다르면, 짧은 것이 먼저 온다.

2. 만약 서로 길이가 같다면, A의 모든 자리수의 합과 B의 모든 자리수의 합을 비교,

작은 합을 가지는 것이 먼저온다. (숫자인 것만 더한다)

3. 만약 1,2번 둘 조건으로도 비교할 수 없으면, 사전순으로 비교한다.

숫자가 알파벳보다 사전순으로 작다.

 

 

 

2. 문제풀이

 

위와 같은 3가지 조건에 따라 주어진 시리얼 번호들을 정렬하는 것이 목표이다.

정렬 문제이므로, 이번에도 C++에 내장된 sort 함수를 이용하면 된다.

sort 함수의 구조는 아래와 같다.

 

sort(a, a+N, compare);

여기서 첫 번째 인자인 a는 정렬을 시작하고자 하는 부분.

두번째 인자인 a+N은 정렬을 끝내고자 하는 부분.

마지막 인자인 compare는 정렬하는 조건을 포함하는 부분이다.

(마지막 compare는 bool 또는 int 형 함수 또는 수식을 이용할 수 있다.

해당 부분은 생략가능하며, 생략 시 오름차순으로 자동 정렬된다.)

 

위와 같이, sort함수의 compare부분에 주어진 시리얼 번호들에 대한 조건을 구현, 적용하면 된다.

작성한 코드는 아래와 같다.

 

 

 

3. 소스코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int cmp(string a, string b) {
	int asize = a.size();
	int bsize = b.size();
	int asum = 0;
	int bsum = 0;

	// 1. 길이가 다르면, 짧은 순서대로 정렬
	if (asize != bsize) {
		return asize < bsize;
	}

	// 2. 길이가 같다면, 합을 이용해 작은 순서대로 정렬
	for (int i = 0; i < a.size(); i++) {
		// 문자열 a에 포함된 숫자들의 합 계산
		if (a[i] >= '0' && a[i] <= '9') {
			asum += int(a[i]) - 48;
		}

		// 문자열 b에 포함된 숫자들의 합 계산
		if (b[i] >= '0' && b[i] <= '9') {
			bsum += int(b[i]) - 48;
		}
	}

	if (asum != bsum) {
		return asum < bsum;
	}


	// 3. 1,2 로 비교 불가능하다면, 사전순으로 비교
	return a < b;

}

int main() {
	int N;
	string serial[50];

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> serial[i];
	}

	// 위에서 정의한 조건함수 cmp에 따라 정렬
	sort(serial, serial + N, cmp);
	for (int i = 0; i < N; i++) {
		cout << serial[i] << "\n";
	}
	
	return 0;
}

우선, sort 함수의 compare부분에 들어갈 cmp 함수를 작성했다.

문제에서 주어진 3가지의 조건에 따라, 다음과 같이 구현했다.

 

1. 길이가 다르면, 짧은 순서대로 정렬

: 매개변수로 받은 문자열 a와 b의 길이를 비교해, 같지 않을 시,

짧은 순서대로 정렬되도록 return.

 

2. 길이가 같다면, 합을 이용해 작은 순서대로 정렬

: for문을 이용해 문자열 a와 b의 숫자부분의 합을 계산하고,

숫자들의 합이 작은 순서대로 정렬되도록 return.

(for문 안에 int(a[i]) - 48; 을 해준 이유는

int(a[i])로 형변환 시, 해당 문자값에 해당하는 숫자가 나오기 때문에

아스키코드값인 48을 빼주었다.)

3. 1,2 로 비교 불가능하다면, 사전순으로 비교

: 위 두가지 경우로 비교가 되지 않을 시, 사전순으로 정렬되도록 return.

 

위와 같이 cmp 함수를 작성한 후,

메인 함수에서 기타의 개수(N)와 각 기타의 시리얼 번호(serial)를 입력받는다.

이후, sort 함수를 통해 조건에 따라 시리얼 번호를 정렬해주었다.

 

 

---

정렬하는 조건의 부분만 잘 구현해주었다면 어렵지 않은 문제였다.

이제 정렬알고리즘은 뭔가 감이 잡히는 것 같기도 하다..🤔

그런데 왜 아직도 bfs, dfs 는 어렵기만 할까..😥