BOJ 7785 : 회사에 있는 사람 (vector, erase)

삼성 B형 전체 링크

 

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

 

 

vector를 이용한 방법에서 erase도 사용해보자.

vector.erase(pointer)를 이용하면 해당 원소를 삭제할 수 있다.

 

leave 구현 부분을 아래의 코드로 바꾸면 된다.

else /* leave 입력 */
{
	ull h = getHash(name.c_str());

	int size = Hash[h].size();
	for (int i = 0; i < size; i++)
	{
		if (Hash[h][i]->name == name)
		{
			Hash[h][i]->in = 0; /* in = 0 으로 변경 */
			Hash[h].erase(Hash[h].begin() + i);
			break;              /* 동명이인이 없으므로 종료 */
		}
	}
}

 

이 문제에서는 위의 코드로 무사히 넘어가지만, 사실 매우 위험한 코드이다.

 

size에서 Hash[h].size()를 미리 받았지만 erase가 되면서 size가 바뀌었다. 

따라서 i < size 부분은 매우 위험하다.

이 문제의 경우는 특정 조건에서 삭제 후 break를 했기 때문에 run time error가 발생하지 않는다.

 

아래의 코드를 실행하면, vector의 size가 10에서 도중에 9로 변경되었다.

하지만 여전히 size가 10이기 때문에 참조할 수 없는 영역을 참조하게 되어 에러가 나온다.

/* 값이 5인 원소를 삭제하는 코드 */

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
	vector<int> v1;

	for (int i = 0; i < 10;i++) v1.push_back(i);

	int size = v1.size();
	for (int i = 0; i < size; i++)
	{
		if (v1[i] == 5) v1.erase(v1.begin() + i);
		else printf("%d ", v1[i]);
	}
	putchar('\n');

	return 0;
}

 

따라서 변경된 size를 매번 체크하도록 바꾼다고 생각할 수도 있다.

//for (int i = 0; i < size; i++)
for (int i = 0; i < v1.size(); i++)

 

하지만 실행 결과는 6이 빠져있는 것을 알 수 있다.

erase를 하면서 다음 포인터로 vector가 넘어 갔고, i++로 인해 한번 더 다음 포인터로 넘어가기 때문이다.

---

위의 경우를 해결하기 위해 vector를 iterator로 순회한다.

올바른 삭제 코드는 아래와 같다.

/* 값이 5인 원소를 삭제하는 코드 */

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
	vector<int> v2;

	for (int i = 0; i < 10;i++) v2.push_back(i);

	for (vector<int>::iterator iter = v2.begin(); iter != v2.end(); )
	{
		if (*iter == 5) iter = v2.erase(iter);
		else
		{
			printf("%d ", *iter);
			iter++;
		}
	}
	putchar('\n');
    
	return 0;
}

 

erase가 삭제한 포인터의 다음 포인터를 return하기 때문에, for문에서 iter++을 하지 않는다.

삭제의 조건에서 iter는 erase로 받고, 그렇지 않은 경우만 iter++ 을 하기 때문이다.

 

따라서 삭제를 할 때는 정수형 index보다 iter를 사용하는 것이 좋다.

 

두 삭제 코드를 직접 비교해보자.

/* 값이 5인 원소를 삭제하는 코드 */

#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
	vector<int> v1, v2;

	for (int i = 0; i < 10;i++) v1.push_back(i);
	for (int i = 0; i < 10;i++) v2.push_back(i);

	//int size = v1.size(); /* run time error */
	for (int i = 0; i < v1.size(); i++)
	{
		if (v1[i] == 5) v1.erase(v1.begin() + i);
		else printf("%d ", v1[i]);
	}
	putchar('\n');

	for (vector<int>::iterator iter = v2.begin(); iter != v2.end(); )
	{
		if (*iter == 5) iter = v2.erase(iter);
		else
		{
			printf("%d ", *iter);
			iter++;
		}
	}
	putchar('\n');

	return 0;
}

---

이 문제는 map을 이용하면 더 쉽게 풀 수 있다.