[21.09.02] Hash

- 첫번째 문자열과 두번째 문자열의 가장 긴 중복구간 찾기(출제율 높음)

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
int main()
{
    string a = "ATSBBTYG";
    string b = "GTSBB";

    int len1 = a.length();
    int len2 = b.length();

    unordered_map<string, int>m;


    for (int t = len2; t > 0; t--)  // b의 길이만큼 확인
    {

        // a를 잘라서 등록
        for (int x = 0; x <= len1 - t; x++)  
        {
            string temp = a.substr(x, t); //  0인덱스부터  5개   1 5개..   3 5개
            m[temp] = t;                //  0 4개  1 4개 2 4개 3 4개 4 4개
        }
        // b를 잘라서 확인
        for (int x = 0; x <= len2 - t; x++)
        {
            string temp = b.substr(x, t);     //5개 
            if (m.count(temp) == 1) {        // 0 4개  1 4개
                cout << m[temp];
                return 0;
            }

        }
    }


    return 0;
}

- 각 배열에서 선택한 숫자의 합(어려움)

#include<iostream>
#include<unordered_map>
using namespace std;
unordered_map<int, int > m;
int a[6] = {4,-1,8,3,5,2};
int b[6] = {-4,1,-3,-5,6,1};
int c[6] = {2,7,1,2,9,5};
int d[6] = {4,-3,2,1,7,6};
int main()
{
    for (int y = 0; y < 6; y++)
    {
        for (int x = 0; x < 6; x++)
        {
            int sum = a[x] + b[y];
            m[sum] += 1;
        }
    }
    int result = 0;
    for (int y = 0; y < 6; y++)
    {
        for (int x = 0; x < 6; x++)
        {
            int sum = -(c[y] + d[x]);
            result += m[sum];
        }
    }

    cout << result;


    return 0;
}

- 2차원 배열에서 target 찾기

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

string arr[7] = {
    "asdfasd",
    "asdfasd",
    "asdfasd",
    "asdfAAd",
    "asdfAAd",
    "asdfAAd",
    "asdfasd",
};

string target[3] = {
    "AA",
    "AA",
    "AA",
};  
struct axis {
    int y, x;
};
unordered_map<string, axis>a;
// arr 배열에 target이 있는지 없는지 존재 여부 출력 !!

string getkey(int dy, int dx)
{
    string temp;
    for (int y = 0; y < 3; y++) {
        for (int x = 0; x < 2; x++)
        {
            temp += arr[dy + y][dx + x];
        }
    }
    return temp;
}

string getkey2()
{
    string temp;
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 2; x++)
        {
            temp += target[y][x];
        }
    }
    return temp;
}

void sett()
{
    for (int y = 0; y < 7 - 3; y++)
    {
        for (int x = 0; x < 7 - 2; x++)
        {
            string key = getkey(y, x);
            a[key] = { y,x };
        }
    }
}
int main() {
    sett();

    string key = getkey2();
    if (a.count(key) == 1)cout << "존재";

}

- 입력받은 문자열의 위치 출력하기

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
struct axis {
    int y, x;
};
string arr[3][3] = {
    "r","iu","apa",
    "nct","bp","snsd",
    "yc","bts","am"
};

unordered_map<string, axis>a;
void sett() {
    for (int y = 0; y < 3; y++)
    {
        for (int x = 0; x < 3; x++)
        {
            a[arr[y][x]] = { y,x };
        }
    }

}
int main()
{
    sett();
    string input;
    cin >> input;

    cout << a[input].y << " " << a[input].x;


    return 0;
}

- 문자열

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
unordered_map<string, int>h;

int main()
{
    h["bob"] = 44;
    h["kate"] = 14;
    h["kevin"] = 54;
    h["jane"] = 24;
    h["mark"] = 94;

    string input;
    cin >> input;

    //if (h[input] == 1)cout << "찾음";
    if (h.count(input) == 1)cout << "찾음";
    else cout << "없음";

    //for (auto x = h.begin(); x != h.end(); x++)
    //{
    //    cout << x->first << " " << x->second << endl;
    //}


    //vector<int>vect = { 1,2,3,4,5 };
    //for (auto x = vect.begin(); x != vect.end(); ++x)
    //{
    //    cout << *x;
    //}


    return 0;
}

- STL 사용하기

#include <iostream>
#include <unordered_map>

using namespace std;

unordered_map<int, int>k;

int main() {
	int vect[5] = { 1,2,3,100,7 };
	for (int x = 0; x < 5; x++) {
		k[vect[x]] = 1;
	}

	int n;
	cin >> n;

	if (k[n] == 1) cout << "존재";
	else cout << "없음";

	return 0;
}

- addnode

#include<iostream>
using namespace std;
struct node {
    int a;
    node* next;
};

node* head, * last;
void addnode(int x)
{
    if (head == NULL)
    {
        head = new node();
        head->a = x;
        last = head;
    }
    else {
        last->next = new node();
        last = last->next;
        last->a = x;
    }

}
int main()

{

    for (int x = 1; x < 100; x++)
    {
        addnode(x);
    }



    return 0;
}

- Linked List 사용하기

#include<iostream>
#include<ctime>
using namespace std;
int vect[5] = { 3,2,100,1,4 };

struct node {
    int x;
    node* next;
};
node* head[3], * last[3];
void addnode(int from,int a)
{
    if (head[from] == NULL) {
        head[from] = new node();
        head[from]->x = a;
        last[from] = head[from];
    }
    else
    {
        last[from]->next = new node();
        last[from] = last[from]->next;
        last[from]->x = a;
    }
}

int hashf(int key)
{
    return key % 3;
}


void dat()
{
    for (int x = 0; x < 5; x++)
    {
        int hcode = hashf(vect[x]);
        addnode(hcode, vect[x]);

    }
}
int main()
{
    time_t start = clock();
    dat();
    int n;
    cin >> n;

    int hashcode = hashf(n);
    for (node* p = head[hashcode]; p != NULL; p = p->next)
    {
        if (p->x == n) {
            cout << "발견";
            return 0;
        }
    }
    cout << "미발견";

    cout << (int)(clock() - start) << "ms";

    return 0;
}