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

#문제

1764번: 듣보잡

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

1764번: 듣보잡

 

---

#접근방법

map 자료구조를 사용하면 쉽게 풀 수 있다.

반응형

---

#풀이

#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int main(){
    int N,M,cnt=0;
    string s;
    map<string,int> m;
    map<string,int>::iterator iter;

    scanf("%d %d",&N,&M);

    for(int i=0;i<N+M;i++){
        cin >> s;
        m[s]++;
        if(m[s]==2) cnt++;
    }

    printf("%d\n",cnt);

    for(iter=m.begin();iter!=m.end();iter++)
        if(iter->second==2)
            cout << iter->first << "\n";


    return 0;
}

 

일반 int, double 같은 배열들은 1,2,3...n 정수값으로 배열의 위치를 정한다.

 

하지만 map 자료구조는 문자열로 배열의 위치를 정할 수 있다. 그리고 자동으로 사전순으로 정렬이 된다.

 

따라서 이 문제에 적합한 자료구조라고 할 수 있다.

 

map<string,int> m과 같이 정의를 하면 string을 인덱스로 하는 자료구조가 된다.

 

일반 배열과는 다르게 map<string,int>::iterator 를 사용하여 배열을 탐색해주어야 한다.

 

먼저 N,M을 입력받고 string 자료형인 s를 입력받는다. 문제에서 중복된 사람은 없다고 했으니 m[s]++을 해주고 m[s]가 2가되면 듣도 보도 못한 사람이므로 cnt++을 해준다.

 

그리고 iter로 map을 탐색하면서 iter->second 값이 2이면 iter->first를 출력하면 자동으로 사전순으로 출력이 된다.

---

#성능

---

#정리

문자열을 인덱스로 가질 수 있는 자료구조인 map을 아는것,

 

이를 구현할 수 있는 구현력이 있으면 쉽게 풀 수 있는 문제였다.