[C++] 1764 : 듣보잡

실버 Ⅳ

 

우선 틀린 코드 (런타임 에러 - out of range)

 

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

using namespace std;

int n, m;
vector <string> v1;
vector <string> v2;

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

	string name;

	for (int i = 0; i < n; i++) {
		cin >> name;
		v1.push_back(name);
	}
	sort(v1.begin(), v1.end());


	int low, high, mid;

	for (int i = 0; i < m; i++) {
		cin >> name;
		low = 0;
		high = n;

		while (low <= high) {
			mid = (low + high) / 2;

			if (name < v1.at(mid)) {
				high = mid - 1;
			}
			else if (name > v1.at(mid)) {
				low = mid + 1;
			}
			else if (name == v1.at(mid)) {
				v2.push_back(name);
				break;
			}
		}
	}
	
	sort(v2.begin(), v2.end());
	reverse(v2.begin(), v2.end());

	cout << v2.size() << endl;

	while (!v2.empty()) {
		cout << v2.back() << endl;
		v2.pop_back();
	}

}

 

정답 코드

 

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

using namespace std;

int n, m;
vector <string> v1;
vector <string> v2;


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

	string name;

	for (int i = 0; i < n; i++) {
		cin >> name;
		v1.push_back(name);
	}
	sort(v1.begin(), v1.end());

	for (int i = 0; i < m; i++) {
		cin >> name;

		if (binary_search(v1.begin(), v1.end(), name)) {
			v2.push_back(name);
		}
	}
	
	sort(v2.begin(), v2.end());
	reverse(v2.begin(), v2.end());

	cout << v2.size() << endl;

	while (!v2.empty()) {
		cout << v2.back() << endl;
		v2.pop_back();
	}

}

다른 부분은 binary search(이진 탐색) 구현했냐 안했냐의 차이..

즉 내가 구현한 이진탐색 부분에서 out of range가 일어났다는 뜻...

 

내가 구현한 이진탐색 부분 코드

 

int low, high, mid;

	for (int i = 0; i < m; i++) {
		cin >> name;
		low = 0;
		high = n;

		while (low <= high) {
			mid = (low + high) / 2;

			if (name < v1.at(mid)) {
				high = mid - 1;
			}
			else if (name > v1.at(mid)) {
				low = mid + 1;
			}
			else if (name == v1.at(mid)) {
				v2.push_back(name);
				break;
			}
		}
	}

앗 알아버렸다

high에 n-1을 넣어줘야 하는 것 같은데...

 

맞네ㅠㅠ~

 

일단 오류를 알아낸 생각은 다음과 같다

이 부분에서 out of range가 일어남 -> out of range가 일어날 부분은 v1.at(mid) 밖에 없음

-> 그럼 mid가 0~n-1 사이를 벗어난다는 말이 됨 -> 엥 n-1? 그렇네??

 

아이고.... 이분탐색에서 low와 high는 인덱스!!! 라는걸 왜 자꾸 까먹는지 모르겠다..

꽤 오래걸렸다.. 걍 알고리즘 헤더의 bs 쓰고 말아 버리지ㅋㅋ,,

 

 

-------------

아 그리고 추가로.. 런타임 에러 때문에 구글링 하다가 알아낸 건데

이 문제를 풀 때

n개의 이름과 m개의 이름을 모두 같은 벡터에 담고

사전 순으로 정렬한 후,

벡터의 i번째 요소와 i+1번째 요소가 같은지 확인하는 식으로 해서

푼 사람이 있더라...정말 똑똑하게 푼다..!

 

(문자열의) 중복을 확인할 때

이런 식으로 풀면 좋을 것 같다

 

굳이 문자열의 중복이 아니어도 괜찮으려나?