프로그래머스 Hash 문제풀이 - Java

🍡 Hash

- 임의의 데이터를 고정된 크기의 대표값으로 변환해서 저장하는 것, 데이터를 해시함수(어떤 연산) 통해 해시값을 얻어냄. 

- 해시함수를 어떻게 정의하는지에 따라 다른 데이터여도 하나의 해시값이 될 수도 있음(해시 충돌)

- 객체는 기본적으로 할당된 주소값을 이용하여 해시 값 생성

- 해시 테이블 : 해시 값을 사용하여 이에 대응하는 원본 데이터를 찾을 수 있게 해주는 자료구조로, 역함수는 존재하지 않는다 (해시는 단방향 변환, 충돌을 허용하기 때문에 역함수 존재 x)

- 해시 값으로 원본 데이터에 바로 접근이 가능, 따라서 빠른 시간에 데이터 검색, 삽입, 삭제가 가능하다. 

 

---

🍡 HashSet

- 중복을 허용하지 않는 집합

- 데이터 순서 없음 

- add : 데이터 삽입

- contains : 해당 원소 포함 여부(boolean return)

import java.util.*;
Set<Integer> set = new HashSet<>(); 
set.add(1);
set.add(1); // set은 중복 허용 x, 집합에 변화 x
set.add(2);
set.add(3);

System.out.println(set.contains(1)); // true
System.out.println(set.contains(4)); // false

Iterator<Integer> iter = set.iterator();
while (iter.hasNext()) {
	System.out.println(iter.next());
}
// 1
// 2 
// 3 출력

 

🍡 프로그래머스 - 전화번호 목록 

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

- 모든 전화번호를 set 에 저장해두기

- 한 전화번호 읽고 0 ~ phone_book[i].length()만큼 쪼개서 해당 문자열이 set에 포함되었는지 여부 탐색 

ex) "123"읽음 -> 1있나 탐색 -> 12 있나 탐색 -> 123 있나 탐색 (j걸린 for문이 이 로직임) 

class Solution {
        public boolean solution(String[] phone_book) {
            Set<String> set = new HashSet<>();
            for (int i = 0; i < phone_book.length; i++) {
                set.add(phone_book[i]);
            }

            for (int i = 0; i < phone_book.length; i++) {
                for (int j = 0; j < phone_book[i].length(); j++) {
                    if (set.contains(phone_book[i].substring(0, j))) {
                        return false;
                    }
                }
            }

            return true;
        }
    }

 

 

---

 

🍡 HashMap

- key - value 형태로 이루어짐

- key는 중복 허용하지 않는다. (value는 가능) 중복된 값이 들어오면 덮어씌워짐 

- 데이터 순서 x

- put() : 데이터 삽입

- remove( 키 값 ) : 해당 데이터 삭제

- containsKey( 키 값 ) : 해당 키가 존재하는지 여부 (boolean return) 

- clear() : 전체 요소 삭제

import java.util.*;

Map<String, Integer> map = new HashMap<>();
map.put("나몰빼미", 1);
map.put("브케인", 2);
map.put("수댕이", 3);

map.put("나몰빼미", 4); // 중복 key가 들어오면 원래 값 덮어씌워진다. 
System.out.println(map.get("나몰빼미")); // 4

map.remove("수댕이");
System.out.println(map.containsKey("수댕이")); // false (위에서 제거됨)

Set<String> keySet = map.keySet();
for(String s : keySet) {
	System.out.println(s + " " + map.get(s));
}
// 브케인 2 나몰빼미 4 출력 

map.clear(); // 모든 요소 삭제 
System.out.println(map.size()); // 0

 

 

🍡 프로그래머스  - 폰켓몬 

https://school.programmers.co.kr/learn/courses/30/lessons/1845

프로그래머스

- map에다가 포켓몬 쭉 넣어두기, 이미 있는 애들은 value증가시키기 

- 포켓몬 종류가 (map의 key 개수) 가질 수 있는 포켓몬 수(count)보다 많으면 count를, 종류가 더 적다면 종류 개수를 리턴 

class Solution {
        public int solution(int[] nums) {
            Map<Integer, Integer> map = new HashMap<>();
            int count = nums.length / 2;
            for (int i = 0; i < nums.length; i++) {
                if (map.containsKey(nums[i])) {
                    map.put(nums[i], map.get(nums[i]) + 1);
                } else {
                    map.put(nums[i], 1);
                }
            }

            if (map.keySet().size() > count) {
                return count;
            } else {
                return map.keySet().size();
            }
        }
    }

 

 

 

🍡 프로그래머스 - 완주하지 못한 선수 

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

프로그래머스

- 동명이인 있을 수 있으므로 map 에다가 이름 + 사람 수로 저장해두기 

- 완주자 배열을 돌면서 map에서 value감소시키기, 값이 0이되면 map에서 제거

- map에 남아있는 애만 출력 

import java.util.*;
class Solution {
    public String solution(String[] participant, String[] completion) {
        Map<String, Integer> map = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        
        for (int i = 0; i < participant.length; i++) {
            if (map.containsKey(participant[i])) {
                map.put(participant[i], map.get(participant[i]) + 1);
            } else {
                map.put(participant[i], 1);
            }
        }

        for (int i = 0; i < completion.length; i++) {
            if (map.containsKey(completion[i])) {
                map.put(completion[i], map.get(completion[i]) - 1);
                if (map.get(completion[i]) == 0) {
                    map.remove(completion[i]);
                }
            }
        }
        
        for (String s : map.keySet()) {
            sb.append(s);
        }
        
        return sb.toString();
    }
}