HashSet [자료구조]

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

프로그래머스

이 문제를 풀면서 내가 이제까지 안 지식으로 풀기 어렵다는 생각이 들었다.

이제까지 ArrayList, Stack, HashMap , replaceAll 정규식 등 문제를 풀어가면서 새로운 자바 클래스들을 공부하고 그 도구를 활용해서 알고리즘을 풀었다. 하지만 이 문제는 안풀리는것이다 ㅠㅠ 그래서 결국 다른 사람들이 어떻게 풀었는지를 확인했더니 대부분 HashSet으로 풀었다. 아직 그에관한 지식이 없기에 이번에 확실히 공부하고 넘어가야겠다.

 

 

 

HashSet

중복을 허용하지 않은 Set 인터페이스에서 지원하는 구현 클래스

순서대로 입력X

일정하게 유지X

null 요소 허용O

 

중복을 걸러내는 과정

 

HashSet은 객체를 저장하기 전에 먼저 객체의 hashCode() 메소드를 호출해서 해시  코드를 얻어낸 다음

저장되어있는 객체들의 해시 코드와 비교한 뒤 같은 해시 코드가 있다면 다시 equals() 메소드로 두 객체를 배교해서 true가 나오면 동일한 객체로 판단하고 중복 저장을 하지 않는다.

 

문자열의 경우, 같은 문자열을 같는 String 객체는 동일한 객체로 간주되고 다른 문자열을 갖는 String 객체는 다른 객체로 간주되는데, 그 이유는 String 클래스가 hashCode()와 equals() 메소드를 재정의해서 같은 문자열의 경우 hashCode()의 리턴 값을 같게, equals()의 리턴 값은 true가 나오도록 했기 때문이다.

 

HashSet 변수 선언

HashSet<데이터타입> 변수명 = new HashSet<데이터타입>(); 

//뒤에 빈 HashSet 사용시 데이터타입 생략 가능
HashSet<String> set = new HashSet<>();

//초기 용량(Capacity) 설정
HashSet<String> set = new HashSet<>(10);

//다른 HashSet의  모든 값을 가진 HashSet 생성
HashSet<String> set2 = new HashSet<>(set1);

//리스트에 있는 값들로 초기값 지정
HashSet<String> set = new HashSet<>(Arrays.asList("tiger","lion","fox");

 

HashSet 요소 추가

add() 메소드를 호출하여 값을 추가한다.

HashSet<String> set = new HashSet<>();
set.add("tiger");
set.add("lion");
set.add("fox");

HashSet은 저장 순서가 보장되지 않기에 특정 위치에 값을 추가할 수는 없다.

 

입력되는 값이 존재하지 않으면 추가와 동시에 true반환, 존재하면 false 반환

 

HashSet 크기 구하기

size() 메소드를 사용하여 Hash의 크기를 구할 수 있다.

 

set.size();

 

HashSet 값 삭제

remove(value) 메소드를 사용한다.

HashSet<String> set = new HashSet<>(Arrays.asList("고양이","강아지","비둘기"));

set.remove("비둘기"); // 특정 값 제거

set.clear(); // 모두 제거

 

HashSet 값 출력 - Iterator

Set에는 인덱스로 객체를 가져오는 get(index) 메소드가 없다

전체 객체를 대상으로 한번씩 반복해서 가져오는 반복자(Iterator)를 제공한다.

HashSet<String> set = new HashSet<>(Arrays.asList("먼데이키즈","흰눈","마크툽"));

System.out.print(set); // ["먼데이키즈","흰눈","마크툽"]

Iterator iter = set.iterator();  // Iterator 사용

while(iter.hasNext()){ // 값이 있으면 true 없으면 false

	System.out.println(iter.next());
 
 }

 

Set 컬렉션을 그냥 print하게되면 대괄호로 묶여서 set의 전체갑이 출력된다. 

iterator 는 반복자  이터레이터 인터페이스를 구현한 객체를 말하는데 iterator() 메소드를 호출하면 얻을 수 있다.

Iterator에서 하나의 객체를 가져올 때는 next() 메소드를 사용한다. 

그 전에 hasNext() 메소드로 가져올 객체가 있으면 true를 리턴하고 없으면 false를 리턴하며 확인해야한다.

 

Hash 값 검색

set.contains("카더가든"); // true false 반환

contains 메서드는 해당 value를 가지고 있는지 true false를 반환한다.

 

출처 : 

https://coding-factory.tistory.com/554

(감사합니다 💜)

---

여기까지 알아서 이문제를 풀 수 있다.

신고 결과 받기 

 

어떻게 풀것인가

1. HashMap을 만든다. 신고 당한사람 (String) = 신고한 사람들 (HashSet<String>)  (중복이 안되게 저장된다.)

2. HashMap을 만든다. id_list에 있는 사람(String) = 신고한 정지된 사람 수 (Integer)
일단 모든 사람들의 신고한 정지된 사람수를 0으로 초기값설정한다.
1에서 hashset의 size가 k 이상인 사람에 저장된 신고한 사람들로 하여금 2를 만들수있다.

3. id_list를 탐색하면서 2의 맵에 저장된 정지된 사람수를 순서대로 answer 배열에 저장한다.

 

 

import java.util.Map;
import java.util.Map.Entry;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;


class Solution {
    private Map<String,HashSet<String>> whoreport = new HashMap<>(); // 신고 당한 유저에 신고한 유저들을 저장한다.
    private Map<String,Integer> mailcnt =  new HashMap<>(); // 아이디별로 메일받는 수를 저장한다.
    public int[] solution(String[] id_list, String[] report, int k) {
        int[] answer = new int[id_list.length];
        for(String rep : report){
            String[] ids = rep.split(" ");
            String reporter = ids[0];
            String reported = ids[1];
            
            whoreport.put(reported,whoreport.getOrDefault(reported, new HashSet<String>(){{
                add(reporter);
            }}));
            whoreport.get(reported).add(reporter);
        }
        for(String id : id_list){
            mailcnt.put(id,0);
        }
        for(Entry<String,HashSet<String>> entry : whoreport.entrySet()){
            String reported = entry.getKey();
            HashSet<String> set = entry.getValue();
            if (set.size()>=k) {
                Iterator<String> iter = set.iterator();
                while(iter.hasNext()){
                    String id = iter.next();
                    mailcnt.put(id,mailcnt.getOrDefault(id,0)+1);
                }
            }
        }
        for(int i=0;i<id_list.length;i++){
            answer[i] = mailcnt.get(id_list[i]);
        }
        return answer;
    }
}

 

정답입니다!!!!

드디어!!!!!!! 프로그래머스 lv1 문제를 다풀었다!!

11월 5일에 LV0을 다풀었으니 10일만에 LV1을 다푼것이다 ㅎㅎ

 

참고로 LV0은 10월 18일 ~ 11월 5일 이니 약 20일동안 풀었다!

 

이제 다음은 LV2!!! 11월 7일 시작한다