[C++] 백준 1764번 듣보잡

어제 엄청 늦게 잠들었는데(해가 뜨기 직전...) 좀 일찍 일어났다 ㅎㅎ

그런 김에 블로그를 켜봤다.(나 점점 무서워지는 걸...)

왜냐하면 나중에 귀찮아질 것을 알기에...

 

그럼 오늘 풀 문제는??

문제

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

1764번: 듣보잡

 

오호... 듣보잡이라...어떤 문제일지 감도 안 잡힌다.

문제를 읽어보니 그냥 듣도 못한 사람과 보도 못한 사람의 수와 그 명단을 사전순으로 출력하라고 하는데, 처음에는 보고 뭔 소리지 했다.

그냥 두 부분에 이름이 공통으로 들어있으면 듣보잡이 되는거니까 2부분에서 중복되어 들어있는 사람의 수와 그 명단을 사전순으로 출력하면 된다.

 

어제 배웠던 map을 사용하면 될 것 같다.

듣도 보도 못한 사람의 명단을 입력을 받고, 보도 못한 사람의 명단을 입력받을 때 중복되는지 확인한 후 그 수와 명단을 출력하면 되겠다!

 

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

int main() {
	int n,m;
	string str;
	map< string, int > list;
	cin >> n >> m;
	//듣도 보도 못한 사람 추가
	for (int i = 0; i < n; i++) {
		cin >> str;
		list[str]++;
	}
	//보도 못한 사람 입력받으며 중복된 사람이 있는지 확인
	while (m--) {
		cin >> str;
		if (list.find(str) != list.end()) {
			list[str]++;	//그럼 듣보잡은 value가 2
		}
	}
	int name_num = 0;
	vector<string> name_list;
	for(auto list_r:list) {
		if (list_r.second == 2) {
			name_num++;
			name_list.push_back(list_r.first);
		}
	}

	cout << name_num << endl;
	for (int i = 0; i < name_num; i++) {
		cout << name_list[i] << endl;
	}

	return 0;
}

ㅎㅎ

드디어 맞았다 ㅠㅠ

처음에는 코드를 실행해봤는데, 이상한 값들이 출력되어서 엄청 당황했다.

그래서 내가 뭘 잘못했나 자세히 살펴봤는데도 모르겠는 것이다..

 

 

 

그렇다면... 내가 map에 대해 잘못 이해한 것 같아서 그 부분부터 찬찬히 살펴보았다.

어제 작성했던 코드들도 다시 살펴보았다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

그런데!!!(쿠궁)

 

map의 메소드 중 find()와 end()를 사용한 부분이 이상하다!!

end()는 마지막 원소 다음의 반복자를 반환하는 함수이다.

find()는 key와 관련된 원소의 반복자를 반환(찾지 못한 경우 end()반복자를 반환한다)

 

 

 

그렇다!! 난 

if (list.find(str) != list.end()) //중복되는 것이 있는 경우

이 부분을

if (list.find(str) == list.end()) //중복되는 것이 없는 경우

이렇게 쓴 것이다!!(충격)

조심해야겠다...

 

 

map의 end() 함수는 이부분에서 확인하였다.

https://kbj96.tistory.com/23

 

그밖에도 

begin()은 첫 번째 원소의 반복자를 반환(map의 원소를 반복자를 이용하여 접근 가능)

clear()은 저장하고 있는 모든 원소를 삭제

insert()는 원소를 추가

size()는 원소의 개수를 반환

erase()는 해당 원소를 삭제

 

 

음음 오늘 유용한 정보를 많이 얻어가는군요 ㅎㅎ.

 

그럼 이제 다른 풀이를 한번 찾아볼까~~~

이 분은 2가지 방법으로 이 문제를 푸셨다.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    map<string, int> ma;
    vector<string> vt;
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n+m; i++) {
        string str;
        cin >> str;
        ma[str]++;
        if (ma[str] > 1)
            vt.push_back(str);
    }
    sort(vt.begin(), vt.end());
    cout << vt.size() << '\n';
    for (auto o : vt)
        cout << o << '\n';

}
출처: https://ongveloper.tistory.com/112 [옹구스투스, 옹벨 일기]

 

첫번째에서는 나처럼 map을 이용해 중복을 찾아주고 vector에 넣으셨다.

오... 그런데 뭔가 나보다 간단하게 잘 만드셨다 ㅎㅎ.

난 듣도 못한 사람과 보도 못한 사람을 따로따로 입력받아줬는데, 이 분은 만약 중복되면 거기서 벡터에 이름을 넣어주셨다. 그리고 처음부터 이동하면서 값을 찾으면 자연스레 사전 순으로 가장 앞서는 이름을 map에서 찾아주는데, 그 과정은 필요없기에 따로 sort함수를 통해 정렬을 해주셨다. 오호라 이렇게도 코드를 작성할 수 있구나! 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    vector<string>v,vt;
    int n, m;
    string s;
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < m; i++) {
        cin >> s;
        if (binary_search(v.begin(), v.end(), s)) {
            vt.push_back(s);
        }
    }
    sort(vt.begin(), vt.end());
    cout << vt.size() << "\n";
    for (auto o : vt) {
        cout << o << "\n";
    }
}
출처: https://ongveloper.tistory.com/112 [옹구스투스, 옹벨 일기]

두 번째로는 이분 탐색을 이용하셨다. 듣도 못한 사람을 입력받아 오름차순으로 정렬한 후 보도 못한 사람을 순서대로 이분 탐색하여 벡터에 넣고 오름차순으로 정렬하셨다.

 

또 다르게 map을 이용하신 분의 코드도 찾아보았다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
int main(){
    int n, m,cnt=0;
    string s;
    vector<string> result;
    map<string, bool> list;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> s;
        list.insert(make_pair(s, true)); 
        //해시 맵에 듣도 못한 사람 넣어줌
    }
    for (int i = 0; i < m;i++){
        cin >> s;
        if(list[s]){
            //해시 맵에 보도 못한 사람이 있으면
            result.push_back(s); // 이름 기록
            cnt++; // 듣보잡 사람 수 세기
        }
    }
    cout << cnt << '\n'; // 듣보잡 사람 수 출력
    sort(result.begin(), result.end()); // 사전 순 정렬
    for (int i = 0; i < result.size(); i++){
        cout << result[i] << '\n'; // 출력
    }
        return 0;
}
출처: https://hagisilecoding.tistory.com/50 [시간빌게이츠, 컴공과고씨]

이 분은 map에 듣도 못한 사람을 넣어준 후 보도 못한 사람의 이름을 넣어주며 중복되면 벡터에 넣어주고 사람 수를 1 증가해주셨다. 그리고 벡터를 정렬한 후 출력해주셨다.

초반에는 나랑 비슷하게 푸신 것 같았는데, 나는 나중에 중복되는 이름을 넣어주고 듣보잡 사람 수를 카운트하였다.

이렇게 풀 수도 있구나~ 나는 어제 배운 것을 다 써먹으려고 하다가 문제를 조금 어렵게 푼 것 같다.

 

ㅎㅎ 오늘도 보람찬 공부였다.