문제

프로그래머스: 폰켓몬

풀이

주어진 폰켓몬 목록에서 최대한 다양한 종류의 폰켓몬을 선택하는 문제. 아래의 2 숫자를 구하고, 더 작은 값이 결과가 된다.

1. 폰멧몬 종류의 개수 파악: Set 자료구조를 활용해 중복된 종류를 제거할 수 있다.
2. 선택 가능한 최대 폰켓몬 수 파악: 주어진 배열의 절반인 N/2 만큼의 폰켓몬을 선택할 수 있다.

💻 결과 코드

import java.util.HashSet;
import java.util.Set;

public class Solution {
	public int solution(int[] nums) {
    	// 1. 폰켓몬 종류를 저장할 Set 생성
        Set<Integer> uniquePokemens = new HashSet<>();
        
        // 2. 배열을 순회하며 Set에 폰켓몬 종류 추가
        for (int num : nums) {
        	uniuePokemons.add(num);
        }
        
        // 3. 선택 가능한 최대 폰켓몬 수 계산
        int maxSelectable = nums.length / 2;
        
        // 4. Set의 크기와 maxSelectble 중 작은 값을 반환
        return Math.min(uniquePokemeons.size(), maxSelectable);   
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {3, 1, 2, 3};
        System.out.println(sol.solution(nums));  // 출력: 2
    }

📗 HashSet

• HashSet
  • java.util 패키지에 포함된 컬렉션 클래스 중 하나.
  • 집합(Set) 자료구조를 구현한 것

특징

1. 중복 허용 안함 : HashSet은 집합(Set)자료 구조이기 때문에 동일한 요소를 중복해서 자장할 수 없다.
2. 순서 유지 안함: 내부적으로 해시 테이블을 사용하기 때문에 요소가 저장된 순서를 저장하지 않는다.
3. 빠른 조회: 해시 테이블을 사용하기 때문에 요소의 추가, 삭제, 검색이 평균적으로 O(1)의 시간 복잡도를 가진다.
4. null 값 허용: 하나의 null 값을 저장할 수 있다.

주요 메서드

1. add(E e): set.add(3);
2. remove(Object o): set.remove(3);
3. contains(Object o): boolean exist = set.contains(3);
4. size(): int size = set.size()
5. isEmpty(): boolean isEmpty =set.isEmpty()
6. clea(): set.clear();

HashSet의 내부 동작

HashSet은 내부적으로 해시 테이블을 사용해 데이터를 저장하고 관리한다. 이를 통해 빠른 검색, 추가, 삭제 작업이 가능하다.

1. 해시 함수 사용: 요소를 HashSet에 추가할 때, 요소의 hashCode() 메서드를 호출하여 해당 요소의 해시 값을 계산한다.
2. 버킷(bucket) 사용: 해시 값에 따라 요소를 특정 버킷에 저장한다. 해시 테이블은 여러 개의 버킷으로 구성되어 있으며, 각 버킷은 해시 값이 같은 요소들을 저장한다.
3. 충돌 처리: 해시 값이 동일한 여러 요소가 있을 수 있다. 이를 해시 충돌이라고 하며, HashSet은 이를 처리하기 위해 체이닝(chaining) 또는 오픈 어드레싱(open addressing) 등의 방법을 사용한다. 자바의 HashSet은 체이닝을 사용하여 각 버킷에 연결 리스트(linked list)또는 트리(tree) 형태로 요소를 저장한다.
4. 검색 및 삭제: 요소를 검색하거나 삭제 할 때도 해시 함수를 사용하여 해당 요소가 저장된 버킷을 찾고, 버킷 내에서 요소를 검색하거나 삭제한다.

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        
        // 요소 추가
        set.add("apple");
        set.add("banana");
        set.add("cherry");

        // 중복된 요소 추가 시 무시됨
        set.add("apple");

        // 요소 출력
        System.out.println(set); // [banana, cherry, apple] (순서는 다를 수 있음)

        // 요소 검색
        System.out.println(set.contains("banana")); // true
        System.out.println(set.contains("grape")); // false

        // 요소 삭제
        set.remove("banana");
        System.out.println(set); // [cherry, apple]
    }
}