[알고리즘] 2870번: 수학숙제

0. 문제

2870번: 수학숙제

 

---

1. 문제 이해

 

1. 숫자와 알파벳 소문자로 되어있는 글자가 N 줄 있다. → 아스키코드 사용해서 숫자와 알파벳 구분
2. 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다. → 숫자면 문자열에 추가. 알파벳이면 문자열이 비어있지 않다면 vector에 추가하고 문자열 초기화.
3. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다. 하지만 000은 0이다. → int로 변환하기.
4. 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야 한다. → stable_sort() 수행.

 

---

2. 제출

 

가. 틀렸습니다.

//백준 2870번: 수학숙제
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>

using namespace std;

int n;
vector<int> v;

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

    cin >> n;
    for(int i=0; i<n; i++){
        string str, tmp;
        cin >> str;
        for(char c : str){
            if(c >= 95){
                if(tmp.length() > 0){
                    v.push_back(atoi(tmp.c_str()));
                    tmp ="";
                }
            }else{
                tmp += c;
            }
        }
        if(tmp.length() > 0) v.push_back(atoi(tmp.c_str()));
    }
    stable_sort(v.begin(), v.end());
    for(int i : v) cout << i << "\n";

    return 0;
}

• if(c >= 95){ : 소문자 a의 ASCII 코드는 95. 문자 0~9까지는 95보단 작음.
• atoi(tmp.c_str()) : string을 int로 변환. cstdlib가 필요함.

 

각 줄은 최대 100글자이기 때문에 최악의 경우 100글자 모두 숫자일 수 있다.

 

100자리 숫자는 long long으로도 저장할 수 없다.

 

string에서 int로 변환하여 벡터에 저장하지 않는다.

 

불필요한 0을 지운 string으로 저장한다.

 

커스텀 함수를 통해서 벡터를 정렬하도록 수정하자.

 

---

나. 수정

 

//백준 2870번: 수학숙제
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

vector<string> v;
int n;

void go(string& tmp){
    while(true){
        if(tmp.size() && tmp.front() == '0') tmp.erase(tmp.begin());
        else break;
    }
    if(!tmp.size()) tmp = "0";
    v.push_back(tmp);
    tmp = "";
}

bool cmp(string a, string b){
    if(a.size() == b.size()) return a < b;
    else return a.size() < b.size();
}

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

    cin >> n;
    for(int i=0; i<n; i++){
        string str, tmp="";
        cin >> str;
        for(char c : str){
            if(c < 95) tmp += c;
            else if(tmp.size()) go(tmp);
        }
        if(tmp.size()) go(tmp);
    }
    sort(v.begin(), v.end(), cmp);
    for(string s : v) cout << s << "\n";

    return 0;
}

• if(tmp.size() && tmp.front() == '0') tmp.erase(tmp.begin()); : 앞에서부터 0을 지운다.
• if(!tmp.size()) tmp = "0"; : 만약 000인 같은 경우 0이 모두 지워져서 빈 문자열이 된다. 이땐 0을 대입한다.
• else if(tmp.size()) : if(tmp.length() > 0){보다 좋은 방법인 것 같다.
• void go(string& tmp){ : tmp = "";에서 tmp가 call by value인지 reference인지 궁금해서 전역변수로 선언하지 않았다. 결과적으로 string은 call by value였다. 전역변수로 풀면 더 쉽다.

 

    for(char c : tmp){
        if(c == '0') tmp.erase(tmp.begin());
        else break;
    }

위와 같이 처리하면 안된다.

 

도중에 tmp를 수정하기 때문이다.

 

    while(true)
        if(tmp.size() && tmp.front() == '0') tmp.erase(tmp.begin());
        else break;
    }

그래서 while문으로 처리한다.

 

이때 tmp의 size를 매번 확인해야 한다.

 

---