알고리즘 공부 #15 : Hash

Hash Map

Map 컬렉션 클래스 소속
해시 알고리즘 사용
value는 중복가능 key는 고유

HashMap<String,Integer> map=new HashMap<>();
map.put("스트링",1);
for(String str:map.keySet()){
System.out.println(String.format("키:%s,값:%s",str,map.get(key)));
}
map.remove("스트링");
// map.get(key값)이면 value값 나옴 map.keySet()이면 key 값 

• boolean containsKey(Object 키값) : 키값이 있는지 알려준다.
• boolean containsValue(Object 밸류값) : 값이 포함되어있는지 알려준다.

완주하지 못한 선수

프로그래머스 링크

1. HashMap을 이용한 풀이

일단 완주자를 hashmap에 넣고 참가자를 for 돌리면서
1. 존재하지 않는 key값이라면 완주하지못한 한명이기때문에 return 해줌
2. key값이 존재할때 value가 0보다 크면 완주자이름이기때문에 value-1해준다.
0보다 작으면 완주자<참가자이기때문에 이름을 return해준다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        int tmp=0;
        for(String str:completion){
            if(map.get(str)!=null){ //동명이인일경우
                tmp=map.get(str);
                map.put(str,tmp+1);
            }
            else{
                map.put(str,1);
                }
        }
        for(String str:participant){
           
            if(map.get(str)!=null){ //완주한 목록에 이름 있는 사람들이면
                tmp=map.get(str);
                if(tmp>0){
                    map.put(str,tmp-1);
                } 
                else return str;
            }
            else{
                return str;
            }
            
        }
       return "얌"; 
    }
}

2. sort이용한 풀이

sort해준다음 비교해서 다르면 출력해주는것뿐!
주의할 점은 참여자보다 완주자가 더 작기때문에 맨마지막에 참여자가 한명 남으면 그걸 리턴해줘야한다는점이다.

import java.util.*;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
         int i;
        Arrays.sort(participant);
        Arrays.sort(completion);
       
        for(i=0;i<completion.length;i++){
            if(!participant[i].equals(completion[i])){
                
                return participant[i];
            }
            
        }
        return participant[i];
        
    }
}

전화번호 확인

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
     Map<String, Integer> map = new HashMap<>(); 
        for (int i = 0; i < phone_book.length; i++) 
            map.put(phone_book[i], i);  
        for (int i = 0; i < phone_book.length; i++) 
            for (int j = 0; j < phone_book[i].length(); j++) 
                if (map.containsKey(phone_book[i].substring(0, j))) 
                    return false; 
        return true;

    }
}

위장

1. 옷 종류를 key로 저장하고 value로 갯수를 저장한다.
2. 옷종류별로 +1 한것을 곱하고 -1 한것이 답이다.

import java.util.HashMap;

class Solution {
    public int solution(String[][] clothes) {
    	int answer = 1; 

    	HashMap<String, Integer> map = new HashMap<>();
    	
    	for(int i = 0; i < clothes.length; i++) {
    		if(map.get(clothes[i][1]) == null)
    			map.put(clothes[i][1], 1);
    		else
    			map.put(clothes[i][1], map.get(clothes[i][1]) + 1);
    	}
    	
    	for(String keys: map.keySet()) {
    		answer *= (map.get(keys) + 1);
    	}
        
    	answer -= 1;
        
        return answer;
    }
}