(C++) - 백준(BOJ) 4158 : CD

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

4158번: CD

적합한 자료구조를 찾아 자료를 저장해 해결한 문제였습니다.

📕 풀이방법

📔 입력 및 초기화

n, m, 정답을 출력할 ans, unordered_map sangeunCD를 선언한 후 매 test case별로 입력받습니다.

📔 풀이과정

set또는 map은 원소조회에 걸리는 시간복잡도가 logn이 소모됩니다. 최대 100만에 달하는 원소가 input으로 들어오게 되므로 O(100만log100만)은 시간초과에 걸려 틀리게 되는데 이유를 모르겠습니다. 충분히 1초안에 실행될 것 같았는데 말이죠. 이유 아시는 분 댓글 부탁드립니다.

unordered_map은 hash자료구조를 사용하기에 O(1) 만에 조회가 가능해 맞게 되었습니다.

1. 상근이의 cd번호를 key로하고 cd 존재여부를 0또는 1로표시하는 value로 두어 저장했습니다.

2. 이 후 선영이의 cd를 입력받을 때마다 상근이의 unordered_map을 조회하도록 해서 value가 1이라면 동시에 가지고 있는 것으로 판별해 ans++해주었습니다.

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, m, ans;
unordered_map <int,int> sangeunCD;

int main(){
  fastio;
  while(1){
    cin >> n >> m;
    if(!n && !m) break;

    ans = 0;
    sangeunCD.clear();

    for(int i = 0, cd; i < n; i++) {
      cin >> cd;
      sangeunCD[cd] = 1;
    }

    for(int i = 0, sunyoungCD; i < m; i++) {
      cin >> sunyoungCD;
      if(sangeunCD[sunyoungCD]) ans++;
    }
    
    cout << ans << '\n';
  }
}