[백준 1764] 듣보잡

• 안녕하세요. BlockDMask 입니다.

• 연휴도 끝났고;; 많이 쉬었네요;; ㅠㅠ

• 오늘의 문제 풀어보겠습니다.

0. 제목

• 백준 1764 듣보잡

• BOJ 1764 듣보잡

문제 이름이 참.. 듣보잡이라니 ㅎㅎ

1. 문제 설명

듣지도 못한 사람의 명단과, 보지도 못한 사람의 명단이 주어질 때,

듣지도 보지도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력 -- 

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다.

이어서 둘째 줄 부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과,

N+2째 줄부터는 보도 못한 사람의 이름이 순서대로 주어진다.

이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다.

N, M 은 500,000 이하의 자연수이다.

출력 --

듣보잡의 수와 그 명단을 사전순으로 출력한다.

2. 풀이 과정

vector container를 이용하여

N개에 해당하는 듣도 못한 사람의 명단을 받고, STL sort (quick sort)를 이용하여 사전순으로 정렬 합니다.

정렬한 명단에서 새로 받은 M개의 보도 못한 사람을 binary_search를 이용하여 빠르게 찾습니다.

중복된 명단(듣보잡 명단)을 새로운 vector 에 집어 넣고, 

STL sort(quick sort)를 이용하여 사전순으로 정렬 후 출력합니다.

**binary_search 에 대한 포스트는 [여기]있습니다.

3. 코드

//https://www.acmicpc.net/problem/1764
//BOJ_1764_듣보잡
 
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
 
using namespace std;
 
int main(void){
    int n, m;
    scanf("%d %d", &n, &m);
 
 
    vector<string> v;
    vector<string> v_result;
 
    //입력1
    //push_back을 사용하면 2^n제곱으로 메모리(capacity)를 잡습니다.
    //하지만 resize를 이용하면 미리 메모리를 할당하여, 속도를 줄이고 v[i]를 이용하여 입력을 받을 수 있습니다.
    v.resize(n);
    for(int i=0; i<n; i++){
        cin >> v[i];    //빠르게 받기위해 push_back이 아닌 배열처럼 받음
    }
 
    //오름차순으로 정렬
    sort(v.begin(), v.end());
 
    //입력2
    string str;
    for(int j=0; j<m; j++){
        cin >> str;
 
        if(binary_search(v.begin(), v.end(), str)){ //중복값 존재하면 v_result에 삽입
            v_result.push_back(str);
        }
    }
 
    //정렬
    sort(v_result.begin(), v_result.end());
 
    //출력
    printf("%d\n", (int)v_result.size());
    for(int i=0; i<v_result.size(); i++){
        printf("%s\n", v_result[i].c_str());
    }
 
    return 0;
}
 

4. 인증

문제 출처 - https://www.acmicpc.net/problem/1764

감사합니다. 하트 꾹꾹 부탁드립니다.!