[백준] 1764번 듣보잡 (C++) - binary search, map

문제

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

1764번: 듣보잡

코드

binary search 풀이

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

using namespace std;

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

  vector<string> nh;
  vector<string> nhs;

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

  for(int i=0; i<m; i++){
    string b;
    cin >> b;
    int start = 0;
    int end = n-1;
    while(start<=end){
      int mid = (start+end)/2;
      if(nh[mid] == b){
        nhs.push_back(b);
        break;
      }
      else if(nh[mid] < b){
        start = mid+1;
      }
      else{
        end = mid-1;
      }
    }
  }
  sort(nhs.begin(), nhs.end());
  cout << nhs.size() << '\n';
  for(string s : nhs){
    cout << s << '\n';
  }

  return 0;
}

 

map 풀이

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

using namespace std;

int main(){

  int n, m;
  cin >> n >> m;
  map<string, int> dic;

  vector<string> v;
  for(int i=0; i<n+m; i++){
    string s;
    cin >> s;
    dic[s]++;
    if(dic[s] > 1){
      v.push_back(s);
    }
  }
  sort(v.begin(), v.end());

  cout << v.size() << '\n';
  for(string s : v){
    cout << s << '\n';
  }
  return 0;
}

정리

map이란?

각 노드가 key와 value 쌍으로 이루어진 트리

중복을 허용하지 않는다.

C++의 map의 내부 구현은 검색,삽입,삭제가 O(log n)인 레드블랙트리로 구성되어 있다.

 

++ 레드블랙트리 : 자가 균형 이진 탐색으로서 대표적으로은 연관 배열 등을 구혀는 데 쓰이는 자료구조, 복잡한 자료구조지만 실 사용헤서 효율적이고, 최악의 경우에서도 우수항 실행 시간을 보인다.

 

map 기본형태

map<key, value> m;

 

map 기본 메소드

m.begin() : 첫 번째 원소의 iterator 반환

m.end() : 마지막 원소의 iterator 반환

m.clear() : 저장하고 있는 모든 원소 삭제

m.insert() : 원소 추가

m.find() : key와 관련된 원소의 iterator 반환(찾지 못할 경우 end()의 iterator 반환)

m.size() : 원소의 개수 반환

m.erase() : 해당 원소 삭제

참조

https://ongveloper.tistory.com/112

https://life-with-coding.tistory.com/305

https://kbj96.tistory.com/23

https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC