September 7, 2021

문제

알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

예를 들어, K1KA5CB7이라는 값이 들어오면 ABCKK13을 출력합니다.

시간 제한

1초

메모리 제한

128MB

입력 조건

첫째 줄에 하나의 문자열 S가 주어집니다. (1≤S의 길이≤10,000)

출력 조건

첫째 줄에 문제에서 요구하는 정답을 출력합니다.

풀이

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int number;
vector<char> character;

int main() {
    char tmpChar;

    scanf("%c", &tmpChar);

    while (tmpChar != '\\n')
    {
        if (tmpChar >= 'A' && tmpChar <= 'Z') {
            character.push_back(tmpChar);
        } else {
            number += tmpChar - '0';
        }

        scanf("%c", &tmpChar);
    }

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

    for (int i = 0; i < character.size(); ++i) {
        printf("%c", character[i]);
    }

    printf("%d", number);

    return 0;
}

from curses.ascii import isdigit

S = input()
resultStr = ""
sum = 0

for character in S:
    if (isdigit(character)):
        sum += int(character)
    else:
        resultStr += character

print("".join(sorted(resultStr)) + str(sum))

문자를 차례대로 입력받으며 A~Z는 벡터에 삽입하고, 숫자는 값을 더한다. 작업이 완료되면 벡터를 정렬하고 출력한 후 숫자를 출력한다.

시간 복잡도 분석

이 풀이는 벡터의 정렬 시간에 의존한다. 따라서 시간 복잡도는 O(nlgn)이다.