[BOJ 4821, CPP] ページ数カウント

問題リンク

BOJ 4821

分類

実装、文字列、パース

はじめに

最近入社することになって、かなり忙しい日々が続いている。会社にいること自体に負担を感じる新人なので…しばらくは適応にいっぱいになりそうだ！それでも色々な話を地道に書こうと記録しているので、近いうちに語れるはず。

最近 C を学べる良い機会を得たし、Python や Java で時間切れの壁にぶつかるたびに残念な思いをしていたので、これを機に C++ で問題演習を進めてみたいと思った。

短い期間の使用経験ではあるが、実装の多くの場面で手間がかかるとはいえ、それを速さが補ってくれる感覚をかなり受ける。慣れれば速さという長所だけを取り込めるだろうか…？楽しみだ。

解説

• vector: 動的配列構造で、配列に似ているがサイズを動的に変えられ、メモリ確保が自動という大きな利点がある！

• npos: no position、有効でない位置をチェックするためのインデックス値

• stringstream: 文字列をストリームとして扱うための仕組みで、入出力と同じ方式で扱えるため、パースによく使われる

基本ロジックは、ページ数の上限分の範囲をカバーできる bool 配列を作り、入力で来たページ範囲をすべてチェックし、最後にカウントした値を出力するだけだ。

ただし問題で提示される数値範囲が int を超える値で与えられる可能性があるため、それを制御する変数設定が必要であり、範囲が逆順で与えられた場合はチェックしないという例外も注意する必要がある。

こういった処理を Python で解くときはとても楽だったが、C++ にしたところコードがかなり長くなってしまった…

解法コード

// ページ数え

#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int				total_page, seperator, start, end, result;
	string			temp, each_range;
	vector<string>	line_info;
	vector<bool>	print_info;
	vector<int>		result_vector;

	while (true)
	{
		cin >> total_page;

		if (!total_page)
			break ;
		else
		{
			print_info.assign(1001, false);
			cin.ignore();
			getline(cin, temp);
			stringstream range_stream(temp);

			while (getline(range_stream, each_range, ','))
			{
				if (each_range.find('-') == string::npos)
				{
					if (each_range.length() < 5 && stoi(each_range) <= 1000)
						print_info[stoi(each_range)] = true;
				}
				else
				{
					seperator = each_range.find('-');
					if (each_range.substr(0, seperator).length() < 5
						&& stoi(each_range.substr(0, seperator)) <= 1000)
						start = stoi(each_range.substr(0, seperator));
					else
						start = 1001;
					if (each_range.substr(seperator + 1, each_range.size()).length() < 5
						&& stoi(each_range.substr(seperator + 1, each_range.size())) <= 1000)
						end = stoi(each_range.substr(seperator + 1, each_range.size()));
					else
						end = 1001;
					if (start <= end)
					{
						for (int i = start; i <= end; i++)
						{
							if (i <= total_page)
								print_info[i] = true;
						}
					}
				}
			}

			result = 0;
			for (int i = 1; i <= total_page; i++)
			{
				if (print_info[i])
					result++;
			}
			result_vector.push_back(result);
		}
	}

	for (int i = 0; i < (int) result_vector.size(); i++)
		cout << result_vector[i] << endl;

	return (0);
}