문제

BOJ 5648, 역원소정렬

핵심

• 입력의 크기가 $10^6$이라 대략 $O(N\times\log_2N)$ 이하의 알고리즘을 사용한다.
• 모든 원소를 거꾸로 뒤집고, 그 원소를 오름차순으로 정렬해야 한다. 단, 뒤집었을 때 숫자가 0으로 시작한다면 0을 지워주는 작업을 해야 한다. 0을 지워주는 작업을 하기 위해선 0이 아닌 문자가 시작하는 인덱스를 찾아야 하는데, Java에서는 이를 지원하는 메서드가 없는 반면 C++에는 존재한다. 따라서 Java에서는 정수를 가지고 원하는 출력을 만들었고, C++에서는 문자열 메서드를 통해 쉽게 파싱할 수 있었다.
• 추가로 입력되는 원소가 한 줄에 입력될 수도 있고, 여러 줄에 입력될 수도 있어서 자바에서는 이 부분을 따로 처리해 주어야 한다.

개선

코드

시간복잡도

• $O(N\times log_2N)$

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;

int n;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	vector<ll> nums;
	nums.reserve(1'000'000);
	for (int i = 0; i < n; ++i) {
		string num; cin >> num;
		reverse(num.begin(), num.end());
		size_t idx = num.find_first_not_of('0');
		num.erase(0, idx);
		nums.push_back(stoll(num));
	}
	sort(nums.begin(), nums.end(), [](auto& a, auto& b) {
		return a < b;	
	});
	for (auto e : nums)
		cout << e << '\n';
}

Java

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        ArrayList<Long> nums = new ArrayList<>(1_000_004);
        int n = Integer.parseInt(st.nextToken());
        int cnt = 0;
        while (true) {
            while (st.hasMoreTokens()) {
                String num = st.nextToken();
                nums.add(Long.parseLong(num));
                ++cnt;
            }
            if (cnt == n)
                break;
            st = new StringTokenizer(br.readLine());
        }
        for (int i = 0; i < nums.size(); i++) {
            long cur = nums.get(i);
            long result = 0;
            while (cur != 0)  {
                result *= 10;
                result += cur % 10;
                cur /= 10;
            }
            nums.set(i, result);
        }
        nums.sort((a, b) -> {
            return a.compareTo(b);
        });
        for (var e : nums)
            bw.write(e + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}