프로그래머스 : 해시 (Hash)

1. 폰켓몬

#include <vector>
#include <set>
using namespace std;
set <int> s;
int solution(vector<int> nums)
{
    int answer = 0;
    for(int i=0; i<nums.size(); i++){
        s.insert(nums[i]);
    }
    if(s.size() >= nums.size()/2)
        return nums.size()/2;
    return s.size();
}

여기서는 set을 사용하여 구현하였다

#include <set>
set <int> s;

원소가 삽입되면 자동으로 오름차순(less) 정렬이 되며 원소값은 중복이 되지 않는다. 

s.insert(k);
s.insert(iter, k);

벡터처럼 사용이 가능하나 push_back이 아닌 insert로 값을 삽입한다.

 

#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<int> nums)
{
    int temp = nums.size();
    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());
    
    if(nums.size() >= temp/2)
        return temp/2;
    return nums.size();
}

혹은 erase 함수와 unique 함수를 사용해서 구현할 수 있다. unique 함수를 사용할 땐 sort가 무조건 되어 있어야 한다

 

 

2. 완주하지 못한 선수

string solution(vector<string> participant, vector<string> completion) {
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());
    for(int i =0; i < completion.size(); i++){
        if(participant[i] != completion[i])
            return participant[i];
    }
    return participant[participant.size()-1];
}

sort만 가지고 간단하게 구현할 수 있는 문제이다. 하지만 hash 문제라서 hash 사용법을 찾아보았다

#include <unordered_map>
unordered_map<string, int> map;
map.insert({"key", 1});
 map["key"]++; // value 값 변경

Hash는 unordered_map으로 구현할 수 있다

#include <unordered_map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map <string, int> h;
    for(int i = 0; i < participant.size(); i++){
        if(h.find(participant[i]) == h.end())
            h.insert({participant[i], 1});
        else
            h[participant[i]]++;
    }
    
    for(int i = 0; i<completion.size(); i++){
        h[completion[i]]--;
    }
    
    for(int i = 0; i < participant.size(); i++){
        if(h[participant[i]] > 0)
            return participant[i];
    }
}

hash를 사용하여 없는 경우 저장하고 중복되는 값일 경우 value 값을 증가시켰다.

완주된 선수는 value 값을 감소시켰고 0보다 큰 값이 남아있는 경우 완주하지 못한 선수가 된다.

 

3. 전화번호 목록

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for(int i = 0; i < phone_book.size()-1; i++){
        if (phone_book[i + 1].find(phone_book[i]) == 0)
            return false;
    }
    return true;
}

string의 find 함수는 문자열 내에서 value 값을 찾고 일치하는 값이 있다면 value의 첫번째 인덱스를 반환한다. 찾는 문자가 없으면 sring::npos를 반환한다. (숫자로는 -1이다)

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

bool solution(vector<string> phone_book)
{
    unordered_map<string, int> map;
    for (int i = 0; i < phone_book.size(); i++)
        map[phone_book[i]] = 1; // 모든 값 저장

    for (int i = 0; i < phone_book.size(); i++)
    {
        for (int j = 0; j < phone_book[i].size() - 1; j++)
        {
            string phone_number = phone_book[i].substr(0, j + 1);
            if (map[phone_number]) // 있다면
                return false;
        }
    }
    return true;
}

차례로 앞부터 잘라서 (substr 사용) 존재하는지 확인하는 방식이다. 해쉬 접근은 O(1)이다.

 

4. 의상

int solution(vector<vector<string>> clothes) {
    unordered_map <string, int> map;
    for(int i = 0; i <clothes.size(); i++){
        string s = clothes[i][1];
        if(map.find(s) != map.end())
            map[s]++; 
        else
              map.insert({s, 1});
    }
    int answer = 1;
    for(auto i = map.begin(); i != map.end(); i++){
        answer *= (i->second + 1);
    }
    return answer - 1;
}

그냥 map[s]++을 해도 된다. s가 없을 경우 자동으로 0으로 초기화 해주기 때문이다. 그리고 1을 늘리므로 같은 기능을 하는 것이었다. 

hash는 무조건 주소값으로 접근해야 한다. auto로 작성했으나 실제는 unordered_map <string, int>::iterator이 된다. 

입지 않은 경우까지 해서 경우의 수를 구한 후 아무것도 입지 않았을 때인 한가지 경우를 빼주면 된다.

https://blog.naver.com/PostView.naver?blogId=do9562&logNo=221754890348

[C++] STL unordered_map

 

5. 베스트 앨범

베스트 앨범은 못 풀어서 나중에 추가 예정