[Hash] Map(STL Container) 이해하기 (완주하지 못한 선수, 위장)

들어가기 앞서...

자바스크립트로 Hash를 처리하려면 다음 포스팅을 보자

https://moonsupport.tistory.com/235

Javascript로 Hash 처리하기

사용법

• 헤더 파일
  #include<map>
• 선언
  map<T,T> 변수명
• 추가 및 삭제
  변수명[key] = value : key를 인덱스로 value를 값으로 배열처럼 삽입가능
  insert(make_pair(key,value)) : pair 형태로 추가
  erase(key) : key값에 해당되는 원소 삭제
  clear() : 깔-끔히 삭제
• 조회
  변수명[key] : key값에 해당하는 value를 반환(이 때 value가 여러개일 경우 맨 처음 값만 반환 만약 없다면 0반환)
  find(key) : key값에 해당하는 iterator를 반환
  count(key) : key값에 해당하는 value의 개수를 반환
• iterator
  begin() : 시작 iterator를 반환 (타입은 자료의 시작값의 메모리 주소이다.)
  end() : end iterator를 반환 (타입은 자료의 마지막값 다음 메모리 주소이다. 이는 곧 비어있음을 의미한다. )
• 기타
  empty() : empty라면 true 아니면 false
  size() : 크기의 수를 반환

예제

완주하지 못한선수

< 문제 >

일단

map 대신 unordered_map을 사용하였다.

사용법은 같고 다만 생성과정에서 정렬을 하지 않기 때문에 메모리 상에 절약을 한다고 한다.

그리고

if(strMap.end() == strMap.find(elem))

이 부분이 재밌는데 map에 key값이 없음을 다음과 같이 표현했다.

.end() 메소드는 자료의 마지막값의 다음값인 빈iterator의 메모리를 반환한다.

.find() 메소드 역시 iterator를 반환하는데 이 때 찾지 못할 경우 역시 빈 iterator를 반환한다.  

이를 통해 key값이 없다면 key값을 추가하고

있다면 key값의 value를 하나씩 증가시킨다.

 

이후에

participant에서 map에 아예 없는 값이 나오면 바로 반환하고

아니면 map의 값을 하나씩 떨어뜨리다 보면 짝이 맞지 않는 값 하나가 -1로 떨어져 답이 된다.

#include <string>
#include <vector>
#include <unordered_map>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> strMap;
    for(auto elem : completion){
        if(strMap.end() == strMap.find(elem))
            strMap.insert(make_pair(elem, 1));
        else
            strMap[elem]++;
    }
 
    for(auto elem : participant)
    {
        if(strMap.end() == strMap.find(elem)){
            answer = elem;
            break;
        }
        else{
            strMap[elem]--;
            if(strMap[elem] < 0){
                answer = elem;
                break;
            }
        }
    }
    return answer;

위장

< 문제 >

각각의 key 값들의 value들의 갯수들을 모두 곱해주는 게 답이다.

주목해볼점은 이터레이터의 사용이다.

선언을 위해서는 다음과 같이 사용한다.

unordered_map<string,int>::iterator iter;

반복문을 실행하기 위해선

for(iter = _map.begin(); iter!= _map.end(); iter++){

시작 메모리부터 끝 메모리가 아닐 때까지 하나씩 더해간다.

이때 iterator의 속성인 map의 값을 가져오기 위해서 다음과 같이 사용했다.

iter->second

만약 키값이라면 다음과 같겠다.

iter->first

이는 컴파일러에 따라서 다음과 같이 표현되기도 한다.

*iter.first 혹은 *iter.second

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
 
int solution(vector<vector<string>> clothes) {
    int answer = 1;
    unordered_map<string,int> _map;
    for(int i=0; i<clothes.size(); i++) {
        string key = clothes[i][1];
        string value = clothes[i][0];
        if(_map.end() == _map.find(key)){
            _map.insert(make_pair(key,1));    
        }else{
            _map[key]++;
        }
    }
    unordered_map<string,int>::iterator iter;
    int multi = 1;
    int count = 0;
    for(iter = _map.begin(); iter!= _map.end(); iter++){
        answer = answer + (iter->second * answer);   
    }
    return answer-1;
}

전화번호 목록

해시의 중복을 판단해야 하는 경우

정렬을 통해서 쉽게 해결할 수 있는 경우도 있다.

짧은 길이의 번호가 긴 번호와 중복되기 때문에

정렬 한 후에 for문을 이용해서 비교해주면 된다.

이 때

find 함수는 문자열에 사용되며 문자열 안에 특정 문자열이 있을 경우에는 해당되는 iteator객체 혹은 메모리를

없을 경우에는 last 혹은 string::npos 라는 값을 리턴해주게 된다.

phone_book[j].find(phone_book[i]) != string::npos

고로 위의 경우에는

값이 발견된 경우 조건문을 통과하게 된다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
bool solution(vector<string> phone_book) {
    bool answer = true;
    sort(phone_book.begin(),phone_book.end());
    for(int i=0; i<phone_book.size(); i++){
        for(int j=i+1; j<phone_book.size(); j++) {
            if(phone_book[j].find(phone_book[i]) != string::npos) {
                return false;
            }
        }
    }
    return answer;
}

베스트 앨범

해당 문제는 javascript로 작성하였다.

2번 줄의 배열은 reduce를 이용하여 JSON형태의 배열을 리턴해준다.

이는 값들의 정렬이 필요하기 때문이다.

 

11번째는 각각의 객체에 key에 따른 value의 합을 계산하기 위해서 생성했다.

 

16번째는 totalPlayset을 통해서 구한 합을 

info에 입력해주었다.

 

21번째는 조건에 맞춰 정렬을 했다.

 

33번째부터는 이 중 상위 2개만 가지는 새로운 배열을 생성했고

 

47번째에 답을 생성하였다. 

function solution(genres, plays) {
    const info = genres.reduce((pre,post,index)=> {
        pre[index] = {
            id : index,
            genres : genres[index],
            plays : plays[index]
        }
        return pre; 
    },[])
 
    const totalPlayset =  info.reduce((pre,post,index)=> {
        pre[post.genres] = pre[post.genres] + post.plays  || post.plays
        return pre
    },{})
 
    info.map((value)=> {
        if(totalPlayset[value.genres]){
            value.total = totalPlayset[value.genres]
        }         
    })
    info.sort((a,b)=> {
        if(b.total-a.total != 0){
            return b.total-a.total
        }else {
            if(b.plays - a.plays != 0) {
                return b.plays - a.plays
            }else {
                return a.id - b.id
            }
        }
    })
 
    let temp = ""
    let count = 0;
    const infoAnswer = []
    info.map((value)=>{
        if(temp == value.genres) {
            count++
        }else {
            count = 0
        }
        temp = value.genres
        if(count < 2){
            infoAnswer.push(value.id)
        }
    })
    const answer = infoAnswer.map((value)=> {
        return value
    })
    return answer;
}