[PS] 백준 2870 수학숙제

이번에는 백준 2870번 수학숙제 문제를 풀어보았습니다.

이 문제는 문자열들 안에 섞여 있는 숫자들을 모두 찾아낸 뒤, 이를 비내림차순으로 정렬해서 출력하는 문제입니다.

즉, 한 줄 전체를 숫자로 보는 것이 아니라 문자열 속에서 연속된 숫자 부분만 골라내야 하는 문제였습니다.

또 이번에는 한 가지 방식이 아니라,

처음에 문자열을 가공해서 푸는 방식과, 이후 더 직접적으로 숫자를 추출하는 방식 두 가지로 정리해두었습니다.

---

문제 설명

N개의 문자열이 주어집니다.

각 문자열은 알파벳 소문자와 숫자로 이루어져 있습니다.

여기서 숫자가 등장하면, 가능한 가장 긴 연속된 숫자를 하나의 수로 봐야 합니다.

예를 들어

01a2b3456cde478

이라면 추출되는 숫자는

• 1
• 2
• 3456
• 478

입니다.

이렇게 찾은 모든 숫자를 모아서 비내림차순으로 출력하면 됩니다.

---

풀이 아이디어

이 문제의 핵심은 문자열을 보면서 숫자가 연속되는 구간만 추출하는 것입니다.

그리고 숫자의 크기가 매우 커질 수 있기 때문에, 단순히 int, long long으로 바꾸어 처리하기보다 문자열 형태로 저장한 뒤 정렬 기준을 직접 정의하는 방식이 중요했습니다.

정렬은 다음 기준으로 할 수 있습니다.

1. 길이가 짧은 숫자가 더 작다.
2. 길이가 같다면 사전순으로 비교한다.

단, 숫자 앞의 0은 제거해주어야 합니다.

---

V1 코드

#include <bits/stdc++.h>
using namespace std;
int N;
string extract_number_string(string s) {
    bool is_pre_degit = false;
    string ret = "";
    for (int i=0; i<s.length(); i++) {
        if (isdigit(s[i])) {
            if (is_pre_degit) {
                ret += s[i];
            } else {
                ret = ret + " " + s[i];
            }
            is_pre_degit = true;
        } else {
            is_pre_degit = false;
        }
    }
    return ret;
}

void split(string s, char delim, vector<string> &elems) {

    auto st = 0;
    auto end = s.find(delim);
    string temp;
    while (end != string::npos) {
        temp = s.substr(st, end - st);
        if (!temp.empty()) {
            elems.push_back(temp);
        }
        st = end + 1;
        end = s.find(delim, st);
    }

    temp = s.substr(st);
    if (!temp.empty())
        elems.push_back(temp);

}

bool cmp(string a, string b) {

    if (a.length() != b.length())
        return a.length() < b.length();

    for (int i = 0; i < a.length(); i++) {
        if (a[i] != b[i])
            return a[i] < b[i];
    }

    return false;
}

void delete_zero(vector<string> &elems) {
    if (elems.empty())
        return;
    for (int i=0; i<elems.size(); i++) {
        while (elems[i].length() > 1 && elems[i][0] == '0') {
            elems[i].erase(0, 1);
        }
    }
}
int main() {

    ios_base::sync_with_stdio(false);

    cin >> N;
    vector<string> num_str;
    vector<string> ret;
    for (int i = 0; i < N; i++) {
        string s;
        cin >> s;
        num_str.push_back(extract_number_string(s));
    }

    for (string s : num_str) {
        split(s, ' ', ret);
    }

    delete_zero(ret);

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

    for (string s : ret) {
        cout << s << endl;
    }

    return 0;
}

---

V1 풀이 흐름

1. 각 문자열에서 숫자인 부분만 따로 추출한다.
2. 이때 연속된 숫자는 붙여서 저장하고, 숫자가 끊기는 지점에서는 공백을 넣는다.
3. 이렇게 만든 문자열을 split으로 나누어 각각의 숫자 문자열을 얻는다.
4. delete_zero()로 앞쪽의 0을 제거한다.
5. 사용자 정의 비교 함수 cmp()를 이용해 정렬한다.
6. 정렬된 숫자 문자열들을 출력한다.

---

V1 구현 포인트

1. 숫자 부분만 따로 추출

처음에는 입력 문자열에서 숫자인 부분만 골라내는 방식으로 접근했습니다.

string extract_number_string(string s)

이 함수에서는 숫자가 연속되면 그대로 이어 붙이고,

숫자가 새롭게 시작되면 공백을 먼저 넣은 뒤 숫자를 붙이도록 했습니다.

즉, 나중에 split하기 좋은 형태의 문자열을 먼저 만들어두는 방식입니다.

---

2. 공백 기준으로 숫자 문자열 분리

숫자들 사이를 공백으로 나누어 두었기 때문에,

split() 함수를 이용해 각각의 숫자 문자열을 다시 분리했습니다.

split(s, ' ', ret);

이 과정을 통해 여러 문자열에 들어 있던 숫자들을 하나의 벡터에 모을 수 있었습니다.

---

3. 앞의 0 제거

문제에서는 숫자 앞의 0을 생략할 수 있기 때문에,

정렬 전에 반드시 제거해야 했습니다.

while (elems[i].length() > 1 && elems[i][0] == '0') {
    elems[i].erase(0, 1);
}

예를 들어 007은 7로 바뀌게 됩니다.

---

4. 문자열 비교로 숫자 정렬

이 문제에서는 숫자 길이가 길 수 있어서 atoi, atol 같은 방식으로 직접 숫자로 바꾸는 것이 적절하지 않습니다.

그래서 문자열 상태로 정렬하되, 숫자 크기 순이 되도록 비교 함수를 따로 정의했습니다.

bool cmp(string a, string b)

길이가 다르면 길이가 짧은 것이 더 작은 수이고,

길이가 같으면 앞에서부터 비교해서 더 작은 쪽이 앞에 오도록 했습니다.

---

V2 코드

#include <bits/stdc++.h>
using namespace std;
int N;
vector<string> output;
string s, ret;
void run() {
    while(true) {
        if(ret.size() && ret.front() == '0') {
            ret.erase(ret.begin());
        } else {
            break;
        }
    }

    if(ret.size() == 0)
        ret="0";

    output.push_back(ret);
    ret = "";
}

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

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> s;
        ret = "";
        for (int j=0; j<s.length(); j++) {
            if (s[j] >= '0' && s[j] <= '9') {
                ret += s[j];
            } else if (ret.size()){
                run();
            }
        }
        if (ret.size())
            run();

    }

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

    for (string s : output) {
        cout << s << "\n";
    }
    return 0;
}

---

V2 풀이 흐름

1. 문자열을 한 글자씩 순회한다.
2. 숫자가 나오면 ret에 계속 붙인다.
3. 숫자가 아닌 문자가 나오면, 지금까지 모아둔 ret이 있으면 run()을 호출한다.
4. run()에서는 앞의 0을 제거한 뒤 output에 저장한다.
5. 문자열 끝까지 갔는데도 ret이 남아 있으면 한 번 더 run()을 호출한다.
6. 모든 숫자 문자열을 모은 뒤 정렬해서 출력한다.

---

V2 구현 포인트

1. 문자열을 직접 순회하면서 숫자 추출

두 번째 방식은 숫자만 따로 뽑아내는 과정을 더 직접적으로 처리했습니다.

if (s[j] >= '0' && s[j] <= '9') {
    ret += s[j];
}

숫자가 나오면 ret에 계속 붙이고,

숫자가 아닌 문자를 만나면 지금까지 모아둔 숫자 문자열을 하나의 숫자로 처리합니다.

---

2. 숫자가 끝났을 때 run() 호출

숫자 구간이 끝나는 순간 run()을 호출해서

• 앞의 0 제거
• output에 저장
• ret 초기화

를 한 번에 처리했습니다.

else if (ret.size()){
    run();
}

이 구조로 숫자가 끊기는 지점마다 바로바로 숫자를 확정할 수 있었습니다.

---

3. 문자열 끝부분이 숫자로 끝나는 경우 처리

문자열 끝이 숫자로 끝날 수도 있기 때문에, 반복문이 끝난 뒤 ret이 남아 있다면 한 번 더 run()을 호출해야 했습니다.

if (ret.size())
    run();

이 부분이 없으면 마지막 숫자가 저장되지 않을 수 있습니다.

---

4. 전부 0인 경우 처리

앞의 0을 지우다 보면 문자열이 전부 사라질 수도 있습니다.

예를 들어 000 같은 경우가 그렇습니다.

그래서 run() 안에서 전부 지워졌다면 "0"으로 다시 넣도록 처리했습니다.

if(ret.size() == 0)
    ret="0";

---

문제를 풀면서 정리한 점

1. substr(i, j)의 두 번째 인자

C++의 substr(i, j)에서 두 번째 인자 j는 끝 인덱스가 아니라 길이(length) 입니다.

즉,

s.substr(st, end - st)

는 st부터 end - st 길이만큼 잘라낸다는 뜻입니다.

---

2. atol, atoi를 쓰면 안 되는 이유

이 문제는 숫자 길이가 최대 100글자까지 갈 수 있기 때문에,

atoi, atol 같은 방식으로 숫자로 바꾸면 범위를 넘을 수 있습니다.

그리고 범위를 넘어간 경우 어떤 값이 반환될지 보장되지 않기 때문에,

이 문제에서는 문자열 그대로 다루는 방식이 맞습니다.

---