BOJ 5648 - 역원소 정렬

문제 링크

문제#

모든 원소가 양의 정수인 집합이 있을 때, 원소를 거꾸로 뒤집고 그 원소를 오름차순으로 정렬하는 프로그램을 작성하세요.

단, 원소를 뒤집었을 때 0이 앞에 선행되는 경우는 0을 생략해야합니다.

입력#

첫 번째로 입력되는 건 $n(1 \le n \le 10^6)$으로 사용자가 뒤이어 입력할 원소값을 결정합니다. 입력하는 줄에는 하나의 원소값 뿐만 아니라 여러 원소값도 들어갈 수 있습니다.

단, 입력하는 정수는 10^12을 넘어선 안 됩니다.

출력#

출력문은 위 문제 내용에 나와있는 정렬방법으로 정렬하여 아래 예제 출력을 참고하여 출력하세요.

풀이#

각 수를 문자열로 받은 뒤 뒤집고, 그 결과를 정수로 바꿔 정렬하면 된다. 입력 숫자가 길 수 있으므로 먼저 문자열로 다루는 편이 자연스럽고, 뒤집은 뒤에는 앞쪽의 0이 사라져야 하므로 정수 변환이 잘 맞는다.

코드에서는 모든 입력을 string으로 받아 reverse한 뒤 stoll로 long long 값에 넣는다. 이렇게 모은 값들을 오름차순으로 정렬하고 한 줄에 하나씩 출력한다.

핵심은 원래 숫자의 크기가 아니라 뒤집은 뒤의 값으로 비교해야 한다는 점이다.

코드#

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
string s;
vector<long long> v;
 
void solve() {
	sort(v.begin(), v.end());
	for (long long ll : v)
		cout << ll << '\n';
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s;
		reverse(s.begin(), s.end());
		long long ll = stoll(s);
		v.push_back(ll);
	}
 
	solve();
	return 0;
}

복잡도#

• 시간 복잡도: 수의 개수를 $N$, 최대 자릿수를 $D$라 하면 뒤집기 비용 $O(ND)$와 정렬 비용 $O(N \log N)$이 든다.
• 공간 복잡도: 뒤집은 수를 저장하는 배열로 $O(N)$을 사용한다.

마무리#

역원소 정렬은 원래 값이 아니라 뒤집은 뒤의 값을 기준으로 비교하는 문제다. 문자열로 뒤집고 숫자로 바꾼 다음 정렬하면 앞자리 0 처리까지 자연스럽게 해결된다.