[백준] 2870번 : 수학숙제 | C++

0. 문제

https://www.acmicpc.net/problem/2870

 

---

1. 문제풀이 핵심

이 문제에서는 문자열에서 숫자를 추출하여 정렬된 순서로 출력하는 것이 목표입니다.

중요한 점은 숫자를 추출할 때 불필요한 0을 제거하고, 긴 숫자이기 때문에 문자열로 다루어야 한다는 점입니다.

 

---

2. 문제풀이에 사용된 개념

 

 

2. 숫자 범위 제한으로 인한 문자열 처리

• 최대 100자리의 숫자를 처리하기 위해 string을 사용하여 저장해야 합니다.

3. 문자열 정렬

• 문자열을 정렬할 때는 아스키코드 순서에 따릅니다. 숫자 문자열을 실제 숫자 순서로 정렬하려면 커스텀 비교 연산자를 사용해야 합니다.
• 긴 숫자 문자열의 경우 자리수가 길수록 더 큰 수이며, 자리수가 같다면 단순히 문자열 대소 비교를 사용하면 됩니다.

 

 

string.erase()

문자열에서 특정 문자 지우기

• 방법 A: s.erase(시작 인덱스, 지울 개수)
• 방법 B: s.erase(str.begin()) 처럼 iterator로 접근

//시작 인덱스, 지울 자릿수 개수
s.erase(2,4);

//포인터로 해당 주소의 문자 하나만 삭제하기
s.erase(s.begin())

//iterator를 이용해서 특정 범위 문자열 지우기
s.erase(s.begin(), s.begin()+3);

 

최대 100자리수 숫자 표현하기

숫자 범위 제한으로 인한 문자열 처리

• 최대 100자리의 숫자를 처리하기 위해 string을 사용하여 저장해야 합니다.

int 는 10^9승 -> 10자리수까지 저장 가능

long long은 10^18승 -> 19자리수까지 저장 가능

 

하지만, 100자리수이기 때문에, string 으로 표현해야합니다.

string s ="";

s+= 문자열[i];

 

 

string 을 숫자 비내림차순으로 sort하기 

문자열 정렬 시 주의점
단순히 sort를 사용하면 아스키 코드 기준으로 정렬되어 23이 142보다 큰 것처럼 나올 수 있습니다. 이를 해결하기 위해 자리수와 ASCII 코드 기반 비교를 결합한 커스텀 비교 함수가 필요합니다.

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

 

 

---

 

3. 문제풀이 코드

버전 1. 0까지 res 문자열에 다 추가한 후, 완성된 string에서 앞에 가있는 0만 지워주기

#include<bits/stdc++.h>

using namespace std;

int n;
vector<string> s;
vector<string> res;

bool cmp(string a, string b){
    if(a.size() == b.size()) return a<b;
    return a.size() <b.size();
}
void make_num(string& num){
    while(num.size()>1 && num.front() == '0') num.erase(num.begin());

    res.push_back(num);
    num="";
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 

    cin >>n;
    while(n--){
        string ns;
        cin >> ns;
        s.push_back(ns);
    }

    for(auto i : s){
        string num = "";

        for(int j=0;j<i.size();j++){
            if(i[j]< 65){
                num+=i[j];
            }else if(num.size() != 0){ //숫자가 아닌데, num에 저장되어있는 숫자가 있는 경우
                make_num(num);                
            }
        }
        if(num.size() != 0){
            make_num(num);  
        }
    }

    sort(res.begin(),res.end(),cmp);

    for(auto i : res){
        cout <<i<<'\n';
    }
}

버전 2. 앞에 들어가는 0은 넣지 않기

#include<bits/stdc++.h>

using namespace std;

int n; // <100
vector<string> res;
vector<string> s;

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

    return a.size() < b.size();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); 

    cin >>n;

    for(int i=0;i<n;i++){
        string cs;
        cin >>cs;
        s.push_back(cs);
    }

    for(auto i :s){
        string cur = "";
        bool onlyZero = false;

        for(char j : i){
            if(j<65){ //숫자인 경우
                if(j=='0' && cur.empty()){ 
                    onlyZero=true; 
                    continue;
                }else{
                    cur+= j;
                }
            }else if(cur.size()>0){ //숫자 끝 부분 처리
                if(onlyZero){ onlyZero=false;}
                res.push_back(cur);
                cur ="";
            }else if(onlyZero){ //0 하나인 경우
                res.push_back("0");
                onlyZero=false;
            }
        }

        if(cur.size()>0){ //마지막이 숫자로 끝난경우 처리 
            res.push_back(cur);
        }else if(onlyZero){ //마지막이 0 하나인 경우 처리
            res.push_back("0");
        }
    }

    sort(res.begin(),res.end(),cmp);
    
    for(auto i : res){
        cout << i << '\n';
    }   
}

 

[실수 포인트]

한 싸이클 안에서

bool isTrue = true;

  와 같은 변수를 사용했다면

 if (!isTrue) {
     doSomething();
     isTrue =ture;
 }

 와 같이 사용한 조건변수를 다시 초기화 해주어야 한다. 

 

3-1. 코드 로직 설명

버전 2는 숫자 문자열의 맨 앞에 0이 추가되지 않도록 onlyZero 변수를 사용해 onlyZero가 true일 경우를 0 하나만 숫자로 존재하는 경우라고 판단하여 res 배열에 넣어줍니다.