[정리] 포인터를 사용하는 이유에 대한 개인적인 생각(백준 1920, C++)

 

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

이미 맞았던 문제 이지만 이진탐색 연습할 겸 다시 풀어보았다.

 

기존에 작성했던 코드는 참고하지 않고 다시 풀어보았는데, 다시 맞긴 했지만 몇 회 정도 시간초과 및 틀림이 발생했다.

 

부족했던 부분과 새롭게 깨달았던 부분을 기록하고자 이 글을 쓴다. 이 글이 누군가에게 도움이 되면 좋겠다.

 

기회가 된다면 위의 문제를 풀고 이 글을 읽었으면 좋겠다. 정답으로 인정받은 코드와 틀렸던 코드를 먼저 보자.

 

내가 정답으로 인정받은 코드는 아래와 같다.

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int bsearch(vector<int>*v, int wanted);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, temp;
	vector<int>v;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp;
		cout << bsearch(&v, temp) << '\n';
	}

	return 0;
}
int bsearch(vector<int>*v, int wanted) {
	int start = 0, end = (*v).size() - 1, mid;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if ((*v)[mid] == wanted) return 1;
		if ((*v)[mid] > wanted) end = mid - 1;
		else start = mid + 1;
	}
	return 0;
}

 

틀린 코드는 아래와 같다. (시간 초과 및 답이 틀린 코드)

#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int bsearch(vector<int>v, int wanted);

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m, temp;
	vector<int>v(100001);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> temp;
		cout << bsearch(v, temp) << '\n';
	}

	return 0;
}
int bsearch(vector<int>v, int wanted) {
	int start = 0, end = v.size() - 1, mid;
	while (start <= end)
	{
		mid = (start + end) / 2;
		if (v[mid] == wanted) return 1;
		else if (v[mid] > wanted) end = mid - 1;
		else start = mid + 1;
	}
	return 0;
}

 

다른 점이 보이는가?

다른 점은 1. 함수의 매개변수 중, 벡터를 어떤 식으로 받고 있는지. 2. 벡터의 크기를 미리 지정하는지 여부. 이다.

 

2번 같은 경우는 벡터의 특성상 미리 선언된 빈 공간은 0으로 채워버리기 때문에 나의 실수로 틀린 거라고 볼 수 있다.

 

1번을 보자. 정답 코드는 벡터의 주소를 받고 있고, 틀린 코드는 벡터의 값을 받고 있다.

시간 초과는 여기에서 발생했다.

 

1. 벡터의 값을 받는 경우 (틀린 경우)

벡터의 값을 받게 되면 값이 존재하는 벡터 전체가 복사가 되기 때문에 자칫 큰 사이즈의 벡터를 받을 경우 값 복사에 시간이 오래걸릴 수 있다. 이 점이 시간 초과라는 결과를 낳았다.

 

2. 벡터의 주소를 받는 경우 (맞은 경우)

벡터의 주소를 받게 되면 수많은 데이터를 포함한 벡터일지라도 벡터의 시작 주소만 넘어오기 때문에 값 전체를 복사할 일이 없다. 즉 값 복사에 시간이 소요될 일이 없다는 뜻이다.

 

C언어를 배우며 포인터가 무엇이고 특징이 무엇인지 배웠지만, 오늘 이 문제를 다시 풀어봄으로써 새로운 특징을 하나 더 얻어갔다. 포인터라는 존재가 정말 쓸모 있구나 라는 생각이 오늘 처음 든 것 같다. 처음 배울 때 너무 어려웠어서 그런가....

 

앞으로 나올 문제에도 이 개념을 잊지 말고 적용시킬 수 있어야겠다. 이상~