백준 1269번 (대칭 차집합) c++

문제

 

문제 풀이

두 가지 방법으로 이 문제를 풀 수 있다.

1. Map을 사용하는 방법

2. Hash를 사용하는 방법

 

Map이란?

map은 각 노드가 key와 value로 이루어진 트리이다. 중복을 허용하지 않는게 특징이다.

그리고 map은 검색, 삽입, 삭제 등이 O(logn)인 레드블랙트리로 구성되어 있다.

 

map<key, value> map1;

 

map은 기본적으로 key를 기준으로 오름차순으로 정렬을 한다.

만약 내림차순으로 사용하고 싶다면 map<int, int, greater> map1;로 사용하면 된다.

 

Map 삽입

그리고 map을 삽입할 때 가장 중요한 점은 pair 객체로 넣어야 한다는 것이다.

 

map1.insert(pair<int, int>(1, 2));

 

 

Map 검색

map은 기본적으로 데이터를 찾을 때 iterator를 사용한다.

그래서 map의 멤버함수인 find를 사용했을 때 만약 찾는 값이 존재하면 그 값의 주소를 반환하고 그렇지 않다면 map.end()를 반환한다.

if(map1.find(1) != map1.end()){
	cout << "find\n";
}

else{
	cout << "not find\n";
}

 

 

반복문을 사용할때

기본적으로 데이터에 접근할 때 iterator를 사용한다고 했기 때문에 iterator를 사용해야 한다.

for(auto iter = map1.begin(); iter != map1.end(); iter++){
	cout << iter->first << ' ' << iter->second << '\n';
}

operator []를 사용해도 접근이 가능하긴 하다.

// 단 key 값이 정수형이라면!!!
for(register int i = 0; i < 10; i++){
	map1.insert(pair<int, int>(i, i));
}

for(register int i = 0; i < 10; i++){
	cout << map1[i] << '\n';
}

Map 삭제

map.clear()를 통해 모든 값을 지울 수 있고,

map.erase(iter) iter이 가리키는 원소를 지운다.

map.erase(start, end) start부터 end까지의 원소들을 지운다.

map.erase("Wick") key값을 기준으로 삭제 할 수도 있다.

 

지금까지 map의 사용법에 알아보았고 본격적으로 문제를 풀어보자면

 

문제에서 두 집합이 주어지는데 두 집합 모두 저장할 필요 없이 하나의 집합만 map에 저장한 뒤 다른 집합을 입력받으면서 map에 존재하는지 확인하고 만약 존재한다면 그만큼 값을 빼주면 쉽게 문제가 풀린다.

아예 처음에 result = N + M으로 잡아놓고 map에 존재한다면 2씩 빼준다면 바로 문제가 쉽게 해결된다.

 

#include <bits/stdc++.h>

using namespace std;

int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N, M;

        cin >> N >> M;

        int result = N + M;

        map<int, int> input;

        for(register int i = 0; i < N; i++){

                int temp;

                cin >> temp;

                input.insert(pair<int, int>(temp, 1));

        }

        for(register int i = 0; i < M; i++){

                int temp;

                cin >> temp;

                if(input.find(temp) != input.end()){
                        result -= 2;
                }

        }

        cout << result << '\n';



        return 0;

}

 

Hash를 이용하는 방법은 Map을 이용하는 방법과 논리는 크게 다르지 않지만 Hash를 직접 구현해야한다.

 

Hash

 

Hash는 기본적으로 임의의 길이의 문자열을 받아 고유한 key값을 생성한다.

#define MAX_TABLE 10000 // 내가 필요한 만큼의 테이블 크기로 잡아주면 된다.

int hashing(string input){
		// 정수로 바꿔 주는 함수이다.

        int div = 401; // 이렇게 정수로 바꿀때 특정한 소수들을 이용하면 최대한 key값이 겹치지 않게 만들 수 있다.

        int i = 0;
        int len = input.length();

        while(i != len){
                div = ((div << 5) + (int)input[i]) % MAX_TABLE;
                i++;
        }

        return div % MAX_TABLE;

}

 

그리고 그 key값에 value를 저장한다.

이렇게 저장을 할 때 같은 key값이 나올 수도 있다. 

그래서 그러한 경우에는 Chaning 방법을 써서 해결하면 된다.

Chaning이란 연결리스트를 통해 바로 뒤로 이어서 저장을 한다.

 

삽입

struct Node{
        string num;
        Node *next;
};

Node head[MAX_TABLE];
Node node[MAX_TABLE];
int node_cnt;

void insert_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        Node *target = &node[node_cnt++];
        target->num = input;

        if(temp->next == 0){
                temp->next = target;
        }
        else{
                while(temp->next != 0){
                        temp = temp->next;
                }
                temp->next = target;
        }

        return;

}

 

찾기

int search_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        while(temp->next != 0){

                if(temp->next->num == input){
                        return 2;
                }
                temp = temp->next;

        }

        return 0;

}

 

전체 코드

#include <bits/stdc++.h>

#define MAX_TABLE 300001

using namespace std;

struct Node{
        string num;
        Node *next;
};

Node head[MAX_TABLE];
Node node[MAX_TABLE];
int node_cnt;

int hashing(string input){

        int div = 401;

        int i = 0;
        int len = input.length();

        while(i != len){
                div = ((div << 5) + (int)input[i]) % MAX_TABLE;
                i++;
        }

        return div % MAX_TABLE;

}

void insert_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        Node *target = &node[node_cnt++];
        target->num = input;

        if(temp->next == 0){
                temp->next = target;
        }
        else{
                while(temp->next != 0){
                        temp = temp->next;
                }
                temp->next = target;
        }

        return;

}

int search_list(string input){

        int key = hashing(input);

        Node *temp = &head[key];

        while(temp->next != 0){

                if(temp->next->num == input){
                        return 2;
                }
                temp = temp->next;

        }

        return 0;

}


int main(){

        ios_base::sync_with_stdio(false);
        cin.tie(0);

        int N, M;

        cin >> N >> M;

        int result = N + M;

        string temp;

        for(register int i = 0; i < N; i++){
                cin >> temp;
                insert_list(temp);

        }

        for(register int i = 0; i < M; i++){
                cin >> temp;
                result -= search_list(temp);
        }

        cout << result << '\n';

        return 0;

}