알고리즘 :: 큰돌 :: Chapter2 - DFS/BFS :: 백준 2870 수학숙제

Embedded June·2023년 6월 30일
0
post-thumbnail

문제

문제링크

해설

  • 실버4 난이도 답지않게 신경쓸 사항이나 반례가 은근히 많은 문제입니다.
    1. 0이 앞에 나올 경우, 0을 생략하거나 제거하는 절차가 필요합니다.
    2. 00이나 000같은 0으로만 이루어진 숫자는 0으로 취급해야 합니다.
    3. 문장 끝에 숫자가 있을 때도 적절한 처리가 필요합니다.
    4. 문장이 최대 100글자이므로 숫자는 문자열로 취급해야 오버플로가 나지 않습니다.
    5. 찾은 모든 숫자를 비내림차순으로 정렬해야 합니다.
  • 문장을 한 글자씩 읽으면서 숫자를 만났을 때부터 숫자 문자열에 숫자 문자를 추가합니다. 이때 num_maked라는 숫자를 만들었다는 플래그 변수를 true로 표시합니다.
  • 그 다음에 숫자가 아닌 문자를 만났다면, 숫자를 다 읽은 것입니다. 이때 num_maked가 true라면, numbers 배열에 만든 숫자 문자열을 추가합니다.
    • 이때, 숫자 문자열 서두에 있는 ‘0’은 모두 제거합니다.
    • 하지만, 앞서 설명드린 2번처럼 0으로만 이루어진 숫자에 대한 고려도 빼먹으면 안 됩니다. 만일 ‘0’을 모두 제거하다보니 문자열이 아무것도 남지 않았을 때는 “0” 이라는 문자열을 추가합니다.
  • 한 문장을 읽었다면, 문장 끝에 숫자가 있을 때도 적절한 처리를 하기 위해 한 번 더 처리해주는 것을 잊지맙시다.
  • 저는 람다함수를 이용해서 비내림차순으로 숫자 문자열을 정렬했습니다.
    • 문자열 길이가 길면, 당연히 긴쪽이 숫자가 더 큽니다. 자릿수가 더 크니까요.
    • 문자열이 길이가 같다면, 맨앞부터 하나하나 문자를 비교해야 합니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int N;
	cin >> N;

	vector<string> numbers;

	while (N--) {
		string line;
		cin >> line;

		string num;
		bool num_maked = false;
		for (char c : line) {
			if (isdigit(c)) {
				num += c;
				num_maked = true;
			}
			else if (num_maked) {
				auto it = begin(num);
				while (*it == '0') it++;
				if (it != end(num))
					numbers.emplace_back(num.substr(it - begin(num)));
				else
					numbers.emplace_back("0");
				num_maked = false;
				num.clear();
			}
		}
		// check if there is number in end of line.
		if (num_maked) {
			auto it = begin(num);
			while (*it == '0') it++;
			if (it != end(num))
				numbers.emplace_back(num.substr(it - begin(num)));
			else
				numbers.emplace_back("0");
		}
	}
	// Sort string by numeric ascending order.
	sort(begin(numbers), end(numbers), [](const auto& lhs, const auto& rhs) {
		if (lhs.length() == rhs.length()) {
			for (int i = 0; i < lhs.length(); i++)
				if (lhs[i] != rhs[i]) return lhs[i] < rhs[i];
		}
		return lhs.length() < rhs.length();
	});
	for (const auto& i : numbers) cout << i << '\n';
	return 0;
}

소스코드 링크

결과

람다함수가 잘못 됐는데 엉뚱한 곳을 디버깅 하느라 엄청 틀렸습니다.

profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글