[C++] 해시(Hash)

해시(Hash)

정렬이 필요 없고 빠른 검색을 원할 때 해시를 사용한다.

 

문제

 

https://programmers.co.kr/learn/courses/30/lessons/42576

코딩테스트 연습 - 완주하지 못한 선수

#include <vector>
#include <string>
#include <unordered_map> // 해시맵
using namespace std;

string solution(vector<string> participant, vector<string> completion){
	string answer = "";
	unordered_map<string, int> temp;
    
	for (string name : participant)
		temp[name]++;
	for (string name : completion)
		temp[name]--;
	for (auto pair : temp)
		if (pair.second > 0){
			answer = pair.first;
			break;
		}
	return answer;
}

 

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Longest Substring Without Repeating Characters - LeetCode

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int answer = 0;

        for (int startIndex = 0, endIndex = 0; endIndex < s.size(); ++endIndex) {
            char c = s[endIndex];

            if (hash[c] != 0)
                startIndex = max(startIndex, hash[c]);

            answer = max(answer, endIndex - startIndex + 1);
            hash[c] = endIndex + 1;
        }

        return answer;
    }
};

 

https://leetcode.com/problems/valid-sudoku/

Valid Sudoku - LeetCode

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
public:
    bool isValidSudokuLine(vector<char>& board) 
    {
        unordered_set<char> check;

        for (char value : board) {
            if (value == '.')
                continue;

            if (check.find(value) != check.end()) 
                return false;
            check.insert(value);
        }

        return true;
    }

    bool isValidSudoku(vector<vector<char>>& board)
    {
        vector<char> boardLine1, boardLine2;

        for (int i = 0; i < 9; i++) {
            boardLine1.clear();
            boardLine2.clear();

            for (int j = 0; j < 9; j++) {
                boardLine1.push_back(board[i][j]);
                boardLine2.push_back(board[j][i]);
            }

            if (isValidSudokuLine(boardLine1) == false || isValidSudokuLine(boardLine2) == false)
                return false;
        }

        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++) {
                boardLine1.clear();

                for (int k = 0; k < 3; k++)
                    for (int h = 0; h < 3; h++)
                        boardLine1.push_back(board[i * 3 + k][j * 3 + h]);

                if (isValidSudokuLine(boardLine1) == false)
                    return false;
            }

        return true;
    }
};

 

https://leetcode.com/problems/max-points-on-a-line/

class Solution
{
public:
	int maxPoints(vector<vector<int>>& points)
	{
		if (points.empty()) return 0;

		unordered_map <long long, int > map;

		int ans = 1;
		for(int i=0;i<points.size();++i)
		{
			for(int j=i+1;j<points.size();++j)
			{
				int x1 = points[i][0]; int y1 = points[i][1];
				int x2 = points[j][0]; int y2 = points[j][1];

				int dx = x2 - x1;
				int dy = y2 - y1;

				map[getLineKey(dx, dy)]++;
			}

			for(const auto cnt : map)
			{
				ans = max(cnt.second + 1, ans);
			}
			map.clear();
		}
		return ans;
	}
private :
	static long long getLineKey(int dx, int dy)
	{
		const int gcd = get_gcd(dx, dy);
		long long key = dx / gcd;
		key = key << 32;

		return  key + dy / gcd;
	}

	static int get_gcd(int a, int b) {
		return b == 0 ? a : get_gcd(b, a%b);
	}
};