백준 단계별로 풀어보기 (4)

1차원 배열을 사용하는 문제이다. 대부분의 문제에서 std::vector를 사용해서 매우 편하게 풀 수 있었다.

 

---

https://www.acmicpc.net/problem/10807

10807번 개수 세기

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v;
	v.reserve(100);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		v.push_back(a);
	}
	int key;
	cin >> key;
	auto a = v.begin();
	int cnt{ 0 };
	while (true) {
		a = find(a, v.end(), key);
		if (a == v.end()) break;
		++cnt; ++a;
	}
	cout << cnt;
}

조건에 맞추어 벡터의 최대 길이인 100 만큼을 reserve 하여 복사 과정을 최소화 하였다.

std::find 를 이용해서 입력으로 받은 정수를 찾는다. 컨테이너 v의 반복자 v.end() 가 return 될 때 까지 반복하여 갯수를 세었다.

---

https://www.acmicpc.net/problem/10871

10871번 X보다 작은 수

 

나의 풀이

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

int main()
{
	int n, x;
	cin >> n >> x;

	vector<int> v;
	v.reserve(10000);

	int num;
	for (int i = 0; i < n; ++i) {
		cin >> num;
		v.push_back(num);
	}

	auto a = v.begin();
	while (true) {
		a = find_if(a, v.end(), [&](int n) {
			return n < x;
			});
		
		if (a == v.end()) break;
		cout << *a << ' ';
		++a;
		
	}	
}

람다 함수 캡쳐 기능을 이용해서 입력으로 받은 수보다 작은 수를 찾을 수 있도록 find_if 함수를 이용하였다. 

위 문제와 마찬가지로 해당하는 수가 없어 end() 를 return 하면 반복문을 빠져나가도록 했다.

해당하는 수가 있다면 * 연산자를 이용해서 반복자의 값을 출력하도록 했다.

---

https://www.acmicpc.net/problem/10818

10818번 최소, 최대

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<int> v;
	v.reserve(1000000);

	while (cin >> n)
		v.push_back(n);

	auto max_val = max_element(v.begin(), v.end());
	auto min_val = min_element(v.begin(), v.end());

	cout << *min_val << " " << *max_val;
}

최소 최대 모두 algorithm 함수를 사용하여 문제를 해결했다. 
(STL은 신이에요)

---

https://www.acmicpc.net/problem/2562

2562번 최댓값

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<int> v;
	int num;
	while (cin >> num)
		v.push_back(num);

	auto a = max_element(v.begin(), v.end());
	cout << *a << '\n' << a - v.begin() + 1;
}

(STL은 신이에요2)

---

https://www.acmicpc.net/problem/10810

10810번 공 넣기

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;
	vector<int> v(n, 0);

	for (int i = 0; i < m; ++i) {
		int a, b, c;
		cin >> a >> b >> c;
		for (int j = a-1; j < b; ++j) {
			v[j] = c;
		}
	}
	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << ' ';
	}
}

vector의 opeartor[] 를 이용해서 주어진 범위에 접근해서 값을 대입했다. 

---

https://www.acmicpc.net/problem/10813

10813번 공 바꾸기

 

나의 풀이

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> v(n, 0);

	iota(v.begin(), v.end(), 1);

	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		int temp = v[a-1];
		v[a - 1] = v[b-1];
		v[b-1] = temp;
	}

	for (int i = 0; i < v.size(); ++i) {
		cout << v[i] << ' ';
	}
}

iota를 이용해 바구니의 번호와 같은 공의 번호가 바구니에 들어있도록 하였다.
(바구니의 번호는 1씩 증가하기 때문에)

첫 번째 for 문에서 temp를 이용해서 교환을 수행한다.

---

https://www.acmicpc.net/problem/5597

5597번 과제 안 내신 분..?

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	vector<bool> v(30, false);
	for (int i = 0; i < 30; ++i) {
		int c;
		cin >> c;
		v[c - 1] = true;
	}

	auto a1 = find(v.begin(), v.end(), false);
	auto a2 = find(a1+1, v.end(), false);
	cout << a1 - v.begin() + 1 << endl;
	cout << a2 - v.begin() + 1<< endl;
}

제출 여부를 저장할 bool vector를 선언하고 모두 false로 초기화 한다.

입력으로 들어온 번호의 bool 값을 true 로 셋팅해서 과제 제출 여부를 저장한다.

이후 find 함수로 false가 저장되어 있는 반복자를 반환받아 저장하고,

그 다음 반복자부터 다시 find 함수를 수행하여 가장 작은 수와 큰 수를 연속해서 찾는다.

해당 위치를 출력하기 위해 begin() 함수와의 뺄셈 연산을 수행한다.

나는 0 based indexing 을 했지만, 1 based 가 더 편할 것 같다.

---

https://www.acmicpc.net/problem/3052

3052번 나머지

 

나의 풀이

#include <iostream>
#include <set>

using namespace std;

int main()
{
	set<int> cont;

	int num;
	while (cin >> num) {
		cont.insert(num % 42);
	}

	cout << cont.size();
}

STL의 set은 중복을 허락하지 않는 컨테이너이다. 

이를 이용해서 나머지를 삽입한 후 컨테이너의 사이즈만 출력하면 되는 문제였다.

---

https://www.acmicpc.net/problem/10811

10811번 바구니 뒤집기

 

나의 풀이

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	vector<int> v(n);
	iota(v.begin(), v.end(), 1);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;	// a 부터 b 까지 바구니를 역순으로

		vector<int> temp;
		copy(v.begin() + a - 1, v.begin() + b, std::back_inserter(temp));

		for (auto j = temp.rbegin(); j != temp.rend(); ++j) {
			v[a - 1] = *j;
			++a;
		}
	}

	for (int a : v) {
		std::cout << a << ' ';
	}
}

이전 문제와 같이 iota를 사용해서 각각의 바구니에 1부터 N까지 수를 채워놓았다.

입력으로 받은 두 수를 이용해 temp vector를 만들고 복사한다.

copy를 사용할 때에는 back_inserter 를 사용하여야 size 가 반영된다.

새로 만든 temp vector를 바로 원래 벡터에 역순으로 값을 대입한다. 

rbegin(), rend() 를 사용해서 역순의 반복자를 얻을 수 있다.

---

https://www.acmicpc.net/problem/1546

1546번 평균

 

나의 풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<double> test;
	test.reserve(1000);
	for (int i = 0; i < n; ++i) {
		int score;
		cin >> score;
		test.push_back(score);
	}

	auto max = *(std::max_element(test.begin(), test.end()));

	for (double& elem : test) {
		elem = elem / max * 100;
	}
	
	double sum = std::accumulate(test.begin(), test.end(), static_cast<double>(0));
	
	cout.precision(10);
	cout << sum / test.size();
}

빈번한 vector 복사를 방지하기 위해서 문제에서 주어진 최대 과목의 수 만큼 reserve를 했다.

입력으로 받은 점수들을 vector에 대입하고, max_element로 가장 큰 점수를 찾는다.
이후는 문제에서 주어진 대로 해당 점수를 바탕으로 새로운 평균을 출력한다.

---

 

* 오류 지적은 환영입니다. ^^ *