[BOJ]1269 대칭차집합(S4, C++)

📋 개요 

이번문제는 hash map {key:value}의 빠른 검색으로 문제를 풀 수 있다. 처음에 구현으로 생각하고 문제를 풀었는데 "시간 초과"가 나서 hash map을 안 사용하고 vector로 풀었다.

map의 빠른 검색시간을 활용해서 풀어야하는 문제로 파악하고 바로 코드를 수정했다.

---

🧩 문제

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

1269번: 대칭 차집합

📝  형식 

📥 입력	📤 출력
첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어진다. 각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.	첫째 줄에 대칭 차집합의 원소의 개수를 출력한다.

💡  예제

🔢 번호	📥 입력	📤 출력
1	3 5 1 2 4 2 3 4 5 6	4

 

🥲  내 코드 및 정답코드

---

📖  해설 및 느낀점

#해설

뭐 일단 위에서 설명한 것과 코드를 보면 알겠지만 백터를 4개 선언해서 차집합을 구하는 방식으로 구현을 했더니 시간 초과가 발생했다.

 

각 집합의 원소의 개수는 200,000을 넘지 않으며, 모든 원소의 값은 100,000,000을 넘지 않는다.

 

내가 작성한 코드에 따르면

    //A-B
    for(int i =0 ; i < lenB; i++){
        int x = B[i];
        A1.erase(remove_if(A1.begin(), A1.end(), [x](int i){ return i == x;})
        , A1.end());
    }

 

반복문을 뜯어보면 remove_if의 시간복잡도는 O(n)이고 erase의 시간 복잡도도O(n)이다. 그리고 겉에서도는 선형 for문도 O(n)으로 O(n*n*n)이 나오게 된다. (이렇게 하는게 맞나...? 사실 헷갈린다. 알고계신 분은 적극적인 피드백 부탁드립니다.)

 

그러니깐 시간 초과가 나오지 않을까라고 생각했다...? 먼가 최악의 시간복잡도를 계산하는 방법을 정확히 몰라서 이 부분부터 공부를 다시 하고 코드를 작성후에 나의 시간 복잡도를 계산하는 방법을 학습해야겠다.

 

결론적으로, 나의 코드에는 "시간초과 (TLE) "가 나왔다.

 

그래서 해쉬 방법을 사용해서 푸는 방식으로 변경했고 문제에서 차집합의 합집합을 구하는 문제라는 것을 찾았다.

아래의 표를 보면 더 이해하기 쉽다.

 

 

대칭 집합은 결국 차집합들(A-B, B-A)의 합을 구하는 문제이다. 즉 겹치는 집합의 원소만 삭제해주면 된다는 이야기이다.

그래서 코드를 아래와 같이 작성했다.

 

입력을 받을때마다 값을 포함하고 있는지 없는지를 확인하는 bool값으로 확인하며 원래 있는 값이라면 erase를 하였다.

알고보니 쉬운 문제... 실버가 약간 다 그런 문제인거 같다.

  for(int i =0 ;  i < A+B ; i++){
        int num;
        cin >> num;
        
        if(AB[num] == true) AB.erase(num);
        else AB[num] = true;
        
    }

 

#느낀점

일단, 시간복잡도를 정확히 계산하는 방법을 모르겠다. 이러쿵 저러쿵 해서 계산하는 법은 알겠는데....

그리고 hash map에 대한 자료구조를 알고 있음에도 무지성 vector로 풀어야지 라고 생각했던것이 큰 패착이였던거 같다!

 

차후에 최악의 시간복잡도를 계산하는 방법을 찾아보고 알고리즘할때 부족한 역량을 채워야할거 같다.