2870 : 수학숙제 - stoi, 문자열기반 숫자 대소비교, custom operator

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

2870번: 수학숙제

---

문제요약

문자 사이 숫자 찾아 비내림차순 정렬

 

*비내림차순 : 연속한 두 수가 같을 수도 있음

*오름차순: 연속한 두 수가 같을 수 있는지 모름.

 

난이도

Silver 4

---

풀이 포인트

• 자료형 범위 체크!
  • 최대 범위가 100글자 즉, 100개의 자리수에 해당하는 숫자는 bigint형을 구현해야함.
  • int는 9자리, long long은 18자리밖에 안됌.
  • 따라서 stoi로 바꿀 경우에는 out of range오류가 나게 되는 것.
• 문자열 기반 숫자 대소 비교
  
  • 정수형 대소비교는 <,>로 간단히 구현할 수 있지만
  • 문자열의 경우
    • 1순위: size가 어떤 게 큰지 (자리수비교)
    • 2순위: 왼쪽부터 아스키코드값이 무엇이 큰지 비교 (큰 자리수부터 하나씩 대소 비교)

vector<string> v;

bool cmp(string a, string b)
{
    //size 즉 자릿수 먼저 비교
    if (a.size() == b.size())
        return a < b;

    //왼쪽 끝에서부터 아스키 코드 기반 비교
    return a.size() < b.size();
}

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

---

REVIEW

 

https://machineboy0.tistory.com/171

4659 : 비밀번호 발음하기 - 플래그

 

 

이 문제에서 연속카운트를 셌던 것과 비슷하게, 

이전 문자가 숫자이고, 현재 문자가 문자라면 숫자 연속이 끊어진 것이니 숫자 축적 배열에 넣는 형식으로 짰다.

 

하지만 모범 답안에서는,

현재가 숫자라면 축적,  현재가 숫자가 아니고 축적된 것이 있다면 벡터에 넣는 식으로 조건부를 구성했다.

 

조건부를 else까지 완벽하게 독립사건들로 구성하는 switch문 느낌이 아니라,

• 숫자와 숫자가 아닌 것을 걸러내고,
• 숫자가 아닌 것에서 축적된 게 있니?

조건부를 큰 덩이를 걸러내는 식으로 깔때기 형식으로 머리 좋게 구성하는 것 계속해서 고안해야한다.

---

그리고, 숫자 축적 벡터에 넣기 전에 001을 1로 만들어주는 로직도

나는 substr으로 짰는데, 모범 답안에서는 string을 queue로 pop하는 것 처럼 begin을 erase하는 식으로 구현했다.

---

커스텀 오퍼레이터라고 부르는 sort의 세번째 매개변수도 아직은 익숙하지 않다.

익숙해지도록 공부하기.

---

이 문제에서 가장 중요했던, 자료형의 최대범위들을 대략적으로는 알고 있어야하고 이를 잘 파악해야함..

다 풀어냈다고 생각하고서 out of range 에러에 거듭 마주했을 땐 참 어이없었다

---

CODE

//100글자니까 longlong안되는구나 판단해야함.

#include <bits/stdc++.h>
using namespace std;
int n;
vector<string> v;
string s, ret;

void go()
{
    while (true)
    {
        if (ret.size() && ret.front() == '0')
            ret.erase(ret.begin());
        else
            break;
    }
    if (ret.size() == 0)    //0000을 
        ret = "0";
    v.push_back(ret);
    ret = "";
}

// 문자열 기반으로 숫자 정렬하려면
// 아스키 코드 기반으로 하게되니까

bool cmp(string a, string b)
{
    //size 즉 자릿수 먼저 비교
    if (a.size() == b.size())
        return a < b;

    //왼쪽 끝에서부터 아스키 코드 기반 비교
    return a.size() < b.size();
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> s;
        ret = "";

        for (int j = 0; j < s.size(); j++)
        {
            if (s[j] < 65)// 숫자 판단하는 것
                ret += s[j];
            else if (ret.size())
                go();
        }
        if (ret.size())
            go();
    }
    sort(v.begin(), v.end(), cmp);

    for (string i : v)
        cout << i << "\n";

    return 0;
}