알고리즘 :: 백준 :: 2870 - 수학숙제

 

 

 

 

 

 

 

❔문제

🔗문제링크

🔄 문제 및 입출력 조건 파악

• 1 ≤ N ≤ 100
• 소문자와 숫자로만 이루어진 문자열 길이 ≤ 100

✏️ 문제풀이

생각해야 할 반례가 많아서 조금 복잡한 문제입니다.

반드시 조건을 먼저 정리하고, 어느정도 손코딩을 마친 뒤에 코딩에 들어가야 햇갈리지 않습니다.

 

문자열을 처음부터 끝까지 읽다가 숫자를 만난다면,

• '0'으로 시작하는 숫자인 경우
  • '0'이 아닌 문자 (숫자 또는 소문자)가 나올 때까지 스킵합니다. (단순히 인덱스 변수 증가)
  • 이때 세 가지 경우가 발생합니다.
    1. 다른 숫자를 만난 경우: 아래 '0'으로 시작하는 숫자가 아닌 경우로 이동 후 처리됩니다.
    2. 소문자를 만난 경우: "00000... " 같은 경우였네요, 토큰을 "0"으로 초기화 해줍니다.
    3. 문자열 범위를 벗어난 경우 (즉, 문자열 가장 뒤에 있는 숫자였던 경우): 마찬가지로 "0"으로 초기화 해줍니다.
• '0'으로 시작하지 않는 경우
  • 토큰을 저장할 문자열에 `push_back()` 또는 `+=` 합니다.
  • 소문자를 만날 때까지, 문자열 범위를 벗어날 때까지 반복합니다.

말로 하면 조금 길고 복잡한 편인데, 코드로는 많이 간단하게 표현할 수 있습니다.

if (isdigit(str[i])) {
    if (str[i] != '0') {	// 0이 아닌 경우 - 계속해서 토큰에 push
        while (i < len && isdigit(str[i])) tok += str[i++];
    } else {	// 0인 경우 - 0인 부분 스킵, 모두 0인 경우라면 "0"으로 초기화
        while (i < len && str[i] == '0') i++;
        if (i == len || !isdigit(str[i])) tok = "0";
    }
}

 

이렇게 구한 숫자 토큰들을 정렬해야 합니다.

문자열을 마치 숫자처럼 정렬하는 방법은 ⓐ 길이가 긴 순으로, ⓑ 길이가 같다면 아스키코드 순으로 정렬하면 됩니다.

sort(begin(vec), end(vec), [](const string& lhs, const string& rhs) {
    if (lhs.length() == rhs.length()) return lhs < rhs;
    return lhs.length() < rhs.length();
});

 

람다함수를 사용해서 깔끔하게 표현할 수 있습니다.

📝 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	
	int N;
	cin >> N;
	
	vector<string> vec;
	
	while (N--) {
		string str;
		cin >> str;
		
		for (size_t i = 0, len = str.length(); i < len; ++i){
			string tok = "";
			if (isdigit(str[i])) {
				if (str[i] != '0') {
					while (i < len && isdigit(str[i])) tok += str[i++];
				} else {
					while (i < len && str[i] == '0') i++;
					if (i == len || !isdigit(str[i])) tok = "0";
				}
				i--;	// for문이므로 중복 증가 방지하기 위해 필요합니다.
			}
			if (!tok.empty()) vec.push_back(tok);
		}
	}
	sort(begin(vec), end(vec), [](const string& lhs, const string& rhs) {
		if (lhs.length() == rhs.length()) return lhs < rhs;
		return lhs.length() < rhs.length();
	});
	for (const string& s : vec) cout << s << '\n';
}

 

🔗 코드 링크

🕧 결과