백준 1551 - 수열의 변화

문제링크

• 백준 1551

문제 접근

• 특정 구분자로 이루어진 문자열을 파싱(parsing)하는 방법으로 stringstream 을 선택했다.

의사코드(pseudo-code)

- n, k 입력
- getline(cin, str)
- stringstream ss(str)
- string token // 비어있는 문자열 객체 선언
- vector<int> a(n)
- i = 0
- while getline(ss, token, ',')
	- a[i++] = stoi(token)
- for i=0 to k-1:
	- for j=0 to n-i-2:
		- a[j] = a[j+1] - a[j]
- for i=0 to n-k:
	- a[i] 출력

소스코드 및 분석

전체 코드

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

int main()
{
	int n = 0, k = 0;
	std::cin >> n >> k;
	std::getchar();

	std::string str;
	std::cin >> str;
	std::stringstream ss(str);
	std::string token;
	std::vector<int> a(n);

	int i = 0;
	while (std::getline(ss, token, ',')) {
		a[i++] = std::stoi(token);
	}

	for (int i = 0; i < k; i++) {
		for (int j = 0; j < n - i - 1; j++)
			a[j] = a[j + 1] - a[j];
	}
	for (int i = 0; i < n - k - 1; i++)
		std::cout << a[i] << ",";
	std::cout << a[n - k - 1] << "\n";
}

다른 풀이 - 재귀호출

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
using namespace std;

// 주어진 배열에서 인접한 두 원소의 차이를 이용해 크기가 1 줄어든 새로운 수열을 만든다.
void make_adj_arr(vector<int>& before, int k) {
	//기저사례: k==0
	if (k == 0) {
		for (int i = 0; i < before.size(); i++) {
			cout << before[i];
			if (i < before.size() - 1) cout << ",";
		}
		cout << endl;
		return;
	}

	vector<int> after;
	for (int i = 0; i < before.size() - 1; i++) {
		int val = before[i + 1] - before[i];
		after.push_back(val);
	}
	make_adj_arr(after, k - 1);
}

int main()
{
	int n, k;
	cin >> n >> k;
	string str, token;
	cin >> str;
	stringstream ss(str);
	vector<int> before;
	while (getline(ss, token, ',')) {
		before.push_back(stoi(token));
	}
	make_adj_arr(before, k);
}