[정렬] 백준 2870 :: 수학숙제

수학숙제 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	1383	405	350	32.022%

문제

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

예제 입력 1 

4
43silos0
zita002
le2sim
231233

예제 출력 1 

0
2
2
43
231233

 

    

 문제 풀이

1차 풀이 (  2124 KB,  0 ms)

• 50글자 전부가 숫자인 경우가 있으므로,  정수형 변수는 금지.
• 0000... 형태의 숫자가 검출되면,  0으로 치환.
  

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

using int32 = int32_t;
using int64 = int64_t;

struct line{
        char val[101] = {};

        bool operator< (line& other){
                auto len_this  = strlen(val);
                auto len_other = strlen(other.val);
                if(len_this != len_other) return len_this < len_other;
                return strcmp(val, other.val) < 0;
        }

        char& operator [] (int32_t idx){
                return val[idx];
        }
};

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        vector<line> found;
        line input, temp;
        int32 N;
        int32 line_len, number_len;
        bool numberParse = false, zeroPrefix = false;
        cin >> N;


        for(int i=0; i<N; i++){
                //! 한줄씩 입력 받는다.
                cin >> input.val;
                line_len = (int32) strlen(input.val);

                for(int j=0; j<=line_len; j++){
                        if('0' <= input[j] && input[j] <= '9')
                        {
                                //! 새로운 숫자의 시작점인가?
                                if(!numberParse) {
                                        zeroPrefix = true;
                                        temp = {};
                                        numberParse = true;
                                        number_len = 0;
                                }

                                //! 접두에 아직 0이 지속되고 있는가?
                                if(zeroPrefix && input[j] == '0') continue;
                                else zeroPrefix = false;

                                temp[number_len++] = input[j];
                        }
                        else if(numberParse)
                        {
                                //! 0으로만 이루어져 있었는지 체크한다.
                                if(zeroPrefix) {
                                        found.push_back({'0'});
                                } else {
                                        found.push_back(temp);
                                }
                                numberParse = false;
                                zeroPrefix = true;
                        }
                }
        }

        //! 정렬하고 출력한다.
        sort(found.begin(), found.end());
        for(auto& num : found){
                cout << num.val << '\n';
        }
}