반응형
해당 글에서는 탐색 알고리즘 중 해시 알고리즘에 대해 이해를 돕기 위해 작성한 글입니다.
1) 탐색 알고리즘(Searching Algorithm)
💡 탐색 알고리즘(Searching Algorithm)
- 데이터 구조 내에서 필요한 정보를 빠르게 찾아내는 데 사용되는 알고리즘입니다.
- 탐색 알고리즘의 종류에 따라 데이터의 크기와 구조 그리고 찾고자 하는 정보의 특성에 따라 탐색 시간이 달라질 수 있습니다.
- 따라서 효율적인 탐색 알고리즘을 선택하여 사용하면 비용과 시간을 크게 절약할 수 있습니다.
1. 탐색 알고리즘 종류
종류 | 설명 | 시간복잡도 |
선형 탐색(Linear Search) | 배열이나 리스트를 처음부터 끝까지 순차적으로 탐색하여 원하는 항목을 찾는 탐색 방법입니다. | O(n) |
이진 탐색(Binary Search) | 정렬된 데이터 구조에서 중간 값과 찾고자 하는 값의 대소 관계를 비교하여 탐색 범위를 절반으로 줄여나가는 탐색 방법입니다. | O(logn) |
해시 탐색(Hash Search) | 데이터를 해시 함수를 사용하여 고유한 해시 값으로 변환하고 이 해시 값을 인덱스로 사용하여 데이터를 찾는 탐색 방법입니다. | O(1) |
완전 탐색(Exhaustive Search) | 모든 가능한 경우의 수를 탐색하여 최적의 결과를 찾는 탐색 방법입니다. | 세부 알고리즘 별 각각 다름. |
보간 탐색(Interpolation Search) | 찾고자 하는 키를 이용해 검색 범위를 결정하는 탐색 방법입니다. | O(n) |
[ 더 알아보기 ]
💡 시간 복잡도(Time Complexity)
- 알고리즘이 실행될 때 필요한 ‘입력 값’과 ‘연산 수행 시간’에 따라 효율적인 알고리즘을 나타내는 척도를 의미합니다.
💡 [참고] 탐색 알고리즘에 대해 상세히 궁금하시면 아래의 글들을 참고하시면 도움이 됩니다.
분류 | 알고리즘 | 링크 |
알고리즘 구현시간 | 시간복잡도, 공간 복잡도, 빅오 표기법 | https://adjh54.tistory.com/186 |
탐색 알고리즘 | 선형탐색(Linear Search) | https://adjh54.tistory.com/193 |
탐색 알고리즘 | 이진탐색 | https://adjh54.tistory.com/187 |
탐색 알고리즘 | 완전탐색 : 기본구조 | https://adjh54.tistory.com/196 |
탐색 알고리즘 | 완전탐색 : 종류 | https://adjh54.tistory.com/197 |
탐색 알고리즘 | 완전탐색: 문제로 이해하기 | https://adjh54.tistory.com/227 |
탐색 알고리즘 | 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS) | https://adjh54.tistory.com/328 |
탐색 알고리즘 | 투 포인터 알고리즘 | https://adjh54.tistory.com/398 |
2) 해시 알고리즘(Hash Algorithm)
💡 해시 알고리즘(Hash Algorithm)
- 데이터를 빠르게 저장하고 검색하기 위한 알고리즘으로 ‘키(key)’를 사용하여 ‘데이터 값(value)’을 조회하는 방법을 의미합니다. 이러한 ‘키-값’을 ‘해시 테이블’이라는 데이터 구조에 저장하여 키에 매핑되는 인덱스 값으로 빠르게 찾을 수 있습니다.
- 키는 해시 함수를 통과하여 해시 값으로 변환되며 이 해시 값은 데이터가 저장되는 배열의 인덱스를 결정합니다.
[ 더 알아보기 ]
💡Java의 Collection Framework에 Map이 그럼 해시 알고리즘으로 구성되어 있는 건가?
- Java Collection Framework의 Map의 경우도 키(key)와 값(value)의 쌍 형태로 저장을 하는 형태입니다.
- 키(key)는 해시 함수를 통해 고유한 해시 코드로 변환되고, 이 해시 코드는 데이터가 저장되는 배열의 인덱스를 결정합니다. 따라서, 키를 통해 해당 값을 빠르게 검색할 수 있습니다.
Map<String, Object> resultMap = new HashMap<>();
resultMap.put("key1", "value1");
resultMap.put("key2", "value2");
resultMap.put("key3", "value3");
System.out.println("key1 : " + resultMap.get("key1"));
System.out.println("key2 : " + resultMap.get("key2"));
System.out.println("key3 : " + resultMap.get("key3"));
1. 해시 알고리즘 처리 방식
💡 해시 알고리즘 처리 방식
- key, value의 형태의 해시는 해시 함수를 통해서 key의 값은 ‘고유한 해시값’으로 변환이 됩니다.
- 이 변환된 해시 값을 기반으로 ‘해시 인덱스’를 결정하여 해시 테이블에는 해시 인덱스와 고유한 해시 값이 저장이 됩니다.
- 탐색을 위해서는 key를 호출하면 인덱스를 찾아서 값을 반환해 주기에 빠르게 조회가 가능합니다.
1. 키(Key)
- 문자열 혹은 정수 형태로 구성된 키이며, key-value 형태로 실제 데이터 구조를 가지고 있습니다. 이 중 키는 실제 데이터를 찾기 위해 사용되는 고유 식별자를 의미합니다.
- 해당 과정에서는 Key 값은 해시함수(Hash Function)로 전달되어 처리가 됩니다.
2. 해시 함수(Hash Function)
- 전달받은 키(Key) 값을 통해서 해시 함수가 수행이 됩니다. 이 해시 함수 내에서는 키를 ‘고유한 해시값’으로 변환합니다.
- 또한 변환된 해시 값은 해시 테이블(Hash Table)의 해시 인덱스(Hash Index)로 저장이 됩니다.
3. 해시 테이블(Hash Table)
- 해시 함수로 전달받은 ‘고유한 해시값’을 기반으로 ‘해시 인덱스(Hash Index)’를 결정하고, 해시 값(Hash Value)은 실제 값이 들어갑니다.
- 고유한 해시값을 가지고 있기에 ‘키’를 통해서 빠르게 값을 검색할 수 있습니다.
[ 더 알아보기 ]
💡 Hash Function이 처리된 값을 Hash Table에 저장하는 과정을 보면 저장 순서가 보장되지 않는 거네?
- 해시 알고리즘은 데이터를 빠르게 검색하고 찾기 위한 목적으로 설계된 알고리즘입니다. 이 알고리즘은 키(key)를 해시 함수를 통해 고유한 해시 값으로 변환하는 방식으로 작동합니다. 이 과정에서 키(key)의 원래 순서는 사라지게 됩니다.
- 결과적으로, 해시 알고리즘과 해시 기반의 데이터 구조는 데이터의 빠른 검색과 접근을 우선시하며, 이를 위해 데이터의 입력 순서나 정렬 상태를 보장하지 않습니다. 이러한 특징은 알고리즘의 효율성과 속도를 높이는 데 중요한 역할을 합니다.
2. 해시 함수(Hash Function)
💡 해시 함수(Hash Function)
- 입력된 키 값(Key)을 받아서 해시 함수가 수행이 됩니다. 이 해시 함수 내에서는 키 값을 기반으로 ‘고유한 해시값’으로 변환을 시킵니다.
- 이 변환된 값은 해시 테이블의 해시 인덱스로 저장이 되며, 해시 인덱스는 데이터의 저장 및 검색에 활용이 됩니다.
- 고유한 해시값 데이터는 고정된 길이의 동일한 크기의 데이터로 매핑을 수행합니다. 즉, 키(key)는 고유한 값과 동일한 크기를 갖는 해시로 변환됩니다.
- 하나의 키가 항상 동일한 해시 값을 생성하도록 설계하게 되어 있어서 데이터 검색 시 원하는 데이터를 빠르게 찾아낼 수 있습니다.
- 하지만, 다른 키가 동일한 해시 값을 생성하게 되면 해시 충돌이 발생하게 되며, 이를 처리하기 위한 여러 방법들이 존재합니다.
[ 더 알아보기 ]
💡 해시 키 값이 인덱스와 같이 00, 01로 들어가는 건 예시로 보여주는 거지?
- 맞습니다. 해시 값은 예시로 보여주기 위한 것이며 실제는 '해시 값'이 들어가게 됩니다.
3. 해시 테이블(Hash Table)
💡 해시 테이블(Hash Table)
- '키(key)'와 '값(value)'을 매핑하는 데이터 구조를 가집니다. 이 구조에서 해시 함수를 사용하여 키를 ‘고유한 해시 값’으로 변환되고 이 해시 값은 배열의 ‘인덱스’로 사용됩니다. 따라서 키를 통해 값을 빠르게 검색할 수 있습니다.
- 하지만 서로 다른 키가 동일한 해시 값을 가질 경우, 즉 해시 충돌이 발생할 경우, 체이닝과 같은 방법을 사용하여 충돌을 해결할 수 있습니다.
요소 | 설명 |
키(Keys) | 해시테이블에서 각 값에 대한 고유 식별자로 사용되는 요소. 키는 해시 함수를 통해 고유한 해시 값으로 변환되며, 이 해시 값은 데이터가 저장되는 배열의 인덱스를 결정합니다. |
인덱스(Index) | 해시 값에 따라 결정되는 데이터의 위치. 데이터를 빠르게 찾기 위한 참조 포인트입니다. |
버킷(Buckets) | 해시 테이블에서 해시 값이 동일한 항목들을 저장하는 공간. 버킷은 하나 이상의 키-값 쌍을 저장할 수 있으며, 버킷 안의 키-값 쌍들은 일반적으로 연결 리스트로 관리됩니다. |
4. 해시 충돌(Hash Collision)
💡 해시 충돌(Hash Collision)
- 서로 다른 키가 동일한 해시 값을 가질 때 발생하는 현상입니다. 이는 해시 함수의 특성상 피할 수 없는 문제로 이를 해결하기 위한 다양한 기법들이 존재합니다.
💡 해시 충돌(Hash Collision) 예시
- key = 10, key = 15인 값이 두 개가 존재한다고 가정할 때, 이를 해시 함수(Hash Function)를 통해서 수행을 하면 ‘해시 값’으로 변환이 됩니다.
- 이 변환된 해시 값은 해시 테이블(Hash Table) 내의 해시 인덱스(Hash Index)로 저장이 되는 시점에 ‘동일한 해시 값’을 가지는 문제가 발생합니다.
💡 해시 충동 해결방법(Collision Resolution Technique) 종류
- Separate Chaining (Open Hashing)
- Open Addressing(Closed Hashing)
ㄴ 선형 탐사(Linear Probing)
ㄴ 이차 탐사(Quadratic Probing)
ㄴ 더블 해싱(Duble Hashing)
4.1. Separate Chaining (Open Hashing)
💡 Separate Chaining (Open Hashing)
- 같은 해시 값을 가진 항목들을 연결 리스트로 관리하는 방법을 말합니다. 이 방법은 해시 값이 같은 모든 키-값 쌍을 하나의 연결 리스트에 저장하므로, 충돌이 발생하면 해당 리스트에 추가하는 방식으로 충돌을 해결합니다.
4.2. Open Addressing(Closed Hashing)
💡 Open Addressing(Closed Hashing)
- 해시 테이블에서 충돌이 발생하면, 다른 빈 위치를 찾아 데이터를 저장하는 방법을 말합니다.
- 이 방식은 선형 탐사, 이차 탐사, 더블 해싱 등의 방법이 있습니다.
종류 | 설명 |
선형 탐사(Linear Probing) | 충돌이 발생하면, 연속적인 위치를 검사하여 처음 발견한 빈 공간에 데이터를 저장하는 방식입니다. |
이차 탐사(Quadratic Probing) | 선형 탐사와 비슷하지만, 충돌이 발생하면 제곱 단위로 위치를 이동시켜 데이터를 저장하는 방식입니다. |
더블 해싱(Duble Hashing) | 두 개의 해시 함수를 사용하여 충돌이 발생하면, 두 번째 해시 함수를 사용하여 위치를 이동시키고 데이터를 저장하는 방식입니다. |
💡 [참고] 해시 충돌에 대한 해결방법에 대해 상세히 궁금하시면 아래의 글을 참고하시면 도움이 됩니다
5. 해시 알고리즘의 시간 복잡도
💡 해시 알고리즘의 시간 복잡도
- 배열을 저장하는 데 시간 복잡도는 O(1) 시간이 걸리지만 검색하는 데는 최소한 O(log n) 시간이 걸립니다.
- 이 시간은 짧은 것처럼 보이지만 큰 데이터 세트의 경우 많은 문제가 발생할 수 있으며 이로 인해 Array 데이터 구조가 비효율적입니다.
3) 해시 알고리즘 활용하기 : Map 인터페이스 구현체 (HashMap, HashTable, LinkedHashMap)
💡 해시 알고리즘 활용하기 : HashMap, HashTable, LinkedHashMap
- 해시 알고리즘을 이용하여 Map 인터페이스의 구현체인 HashMap, HashTable, LinkedHashMap Class에 대해 알아봅니다.
클래스/인터페이스 | Map 인터페이스와 관계 | 설명 |
HashMap | 구현체 | Map 인터페이스를 구현한 클래스로, 해싱 기법을 사용하여 키와 값의 쌍을 저장합니다. |
HashTable | 구현체 | Map 인터페이스를 구현한 클래스로, 해싱 기법을 사용하여 키와 값의 쌍을 저장합니다. 동기화된 메소드를 제공하여 스레드에 안전합니다. |
LinkedHashMap | 구현체 | HashMap의 하위 클래스로, 키-값 쌍을 해시맵에 저장하는 동시에 더블 링크드 리스트에도 입력 순서에 따라 저장합니다. |
SortedMap | 상속 인터페이스 | Map 인터페이스의 확장으로, 키의 자연적인 순서로 키-값 쌍을 유지합니다. |
// HashMap
Map<String, Object> hashMap = new HashMap<>();
// HashTable
Map<String, Object> hashtableMap = new Hashtable<>();
// LinkedHashMap
Map<String, Object> linkedHashMap = new LinkedHashMap<>();
// TreeMap
SortedMap<String, Object> sortedMap = new TreeMap<>();
1. HashMap
💡 HashMap
- Map 인터페이스를 구현한 클래스 중 하나로 ‘구현체’를 의미합니다. Hashing 기법을 사용하여 key와 value를 저장하고, 검색 속도가 빠르다는 장점이 있습니다.
- 주요한 특징은 Key와 Value 값에 모두 NULL 값을 허용하여 Key에도 null 값이 들어가거나 Value에도 null 값이 들어갈 수 있습니다.
💡 HashMap 주요 메서드
메서드 | 리턴 값 | 설명 |
put(K key, V value) | V | 키와 값을 맵에 추가 |
get(Object key) | V | 주어진 키에 해당하는 값을 반환 |
size() | int | 맵의 요소 개수 값을 반환 |
entrySet() | Set<Map.Entry<K,V>> | 맵에 있는 모든 키-값 쌍을 반환 |
containsKey(Object key) | boolean | 주어진 키가 맵에 있는지 확인 |
containsValue(Object value) | boolean | 주어진 값이 맵에 있는지 확인 |
remove(Object key) | V | 주어진 키에 해당하는 키-값 쌍을 삭제 |
clear() | 없음 | 맵에서 모든 키-값 쌍을 삭제 |
💡 HashMap 활용 예시
Map<String, Integer> hashMap = new HashMap<>();
// 1. [추가] 키(key) - 값(value) 추가 : HashMap 내에 값을 추가합니다.
hashMap.put("test1", 1);
hashMap.put("test2", 2);
hashMap.put("test3", null);
// 2. [조회] 키(value) 값을 기반으로 값 조회 : HashMap 내에 값을 조회합니다.
int value1 = hashMap.get("test1");
int value2 = hashMap.get("test2");
int value3 = hashMap.get("test3");
System.out.println("test1 : " + value1 + " test2 : " + value2 + " test3 : " + value3);
// 3. [조회] 전체 해시맵의 요소 개수 조회
System.out.println("size :: " + hashMap.size());
// 4. [조회] 키(value) - 값(value) 조회 : HashMap 내에 키와 값을 조회합니다.
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}
// 5. [조회] 전체 해시맵 중 Key 조회 : HashMap 내에 동일한 키 값이 있는지 조회합니다.
if (hashMap.containsKey("test1")) {
System.out.println("test1 exists.");
}
// 6. [조회] 전체 해시맵 중 value 조회 : HashMap 내에 동일한 값이 있는지 조회합니다
if (hashMap.containsValue(100)) {
System.out.println("Value 100 exists.");
}
// 7. [수정] 키(key) - 값(value) 변경 : HashMap 내에 키를 기반으로 값을 변경합니다.
hashMap.put("test1", 100);
hashMap.put("test2", 101);
hashMap.put("test3", 102);
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
// 8. [삭제] 키(key) 값을 기반으로 요소 삭제 : HashMap 내의 요소를 삭제합니다
hashMap.remove("test1");
hashMap.remove("test2");
hashMap.remove("test3");
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
// 9. [삭제] 해시맵의 모든 요소를 삭제합니다.
hashMap.clear();
System.out.println("test1 : " + hashMap.get("test1") + " test2 : " + hashMap.get("test2") + " test3 : " + hashMap.get("test3"));
2. HashTable
💡 HashTable
- Map 인터페이스를 구현한 클래스 중 하나로 ‘구현체’를 의미합니다. HashMap과 마찬가지로 Hashing 기법을 사용하여 Key와 value를 저장합니다.
- HashMap과 다르기게 스레드에 안전(thread-safe)한 동기화된 메서드를 제공합니다. 이는 멀티 스레드 환경에서 여러 스레드가 동시에 HashTable을 수정하지 못하도록 합니다. 따라서 HashTable은 동시성 문제에 대해 더 안전하게 사용할 수 있습니다.
- 또 다른 차이점은 HashTable이 null key 또는 null value를 허용하지 않는다는 점입니다. 이는 HashMap이 null key와 null value를 모두 허용하는 것과 대조적입니다.
💡 Hashtable 주요 메서드
메서드 | 리턴 값 | 설명 |
put(K key, V value) | V | 키와 값을 맵에 추가 |
get(Object key) | V | 주어진 키에 해당하는 값을 반환 |
size() | int | 맵의 요소 개수를 반환 |
keys() | Enumeration<K> | 맵에 있는 모든 키를 Enumeration 형태로 반환 |
containsKey(Object key) | boolean | 주어진 키가 맵에 있는지 확인 |
containsValue(Object value) | boolean | 주어진 값이 맵에 있는지 확인 |
remove(Object key) | V | 주어진 키에 해당하는 키-값 쌍을 삭제 |
clear() | 없음 | 맵에서 모든 키-값 쌍을 삭제 |
💡 Hashtable 활용 예시
Hashtable<String, Integer> hashtable = new Hashtable<>();
// 1. [추가] 키(key) - 값(value) 추가 : Hashtable 내에 값을 추가합니다.
hashtable.put("test1", 1);
hashtable.put("test2", 2);
hashtable.put("test3", 3);
hashtable.put("test4", null); // ** 오류 발생 : Key에 NULL을 허용하지 않음
hashtable.put(null, 4); // ** 오류 발생 : Value에 NULL을 허용하지 않음
// 2. [조회] 키(value) 값을 기반으로 값 조회 : Hashtable 내에 값을 조회합니다.
int value1 = hashtable.get("test1");
int value2 = hashtable.get("test2");
int value3 = hashtable.get("test3");
System.out.println("test1 : " + value1 + " test2 : " + value2 + " test3 : " + value3);
// 3. [조회] 전체 테이블의 요소 개수 조회
System.out.println("size :: " + hashtable.size());
// 4. [조회] 키에 대해 Enumeration을 얻음 : Hashtable 내에 키를 조회합니다.
Enumeration<String> keys = hashtable.keys();
while (keys.hasMoreElements()) {
String key = keys.nextElement();
System.out.println("Key: " + key + ", Value: " + hashtable.get(key));
}
// 5. [조회] 전체 테이블 중 Key 조회 : Hashtable 내에 동일한 키 값이 있는지 조회합니다.
if (hashtable.containsKey("test1")) {
System.out.println("test1 exists.");
}
// 6. [조회] 전체 테이블 중 value 조회 : Hashtable 내에 동일한 값이 있는지 조회합니다.
if (hashtable.containsValue(100)) {
System.out.println("Value 100 exists.");
}
// 7. [수정] 키(key) - 값(value) 변경 : Hashtable 내에 키를 기반으로 값을 변경합니다.
hashtable.put("test1", 100);
hashtable.put("test2", 101);
hashtable.put("test3", 102);
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
// 8. [삭제] 키(key) 값을 기반으로 요소 삭제 : Hashtable 내의 요소를 삭제합니다.
hashtable.remove("test1");
hashtable.remove("test2");
hashtable.remove("test3");
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
// 9. [삭제] 테이블의 모든 요소를 삭제합니다.
hashtable.clear();
System.out.println("test1 : " + hashtable.get("test1") + " test2 : " + hashtable.get("test2") + " test3 : " + hashtable.get("test3"));
💡 [참고] HashMap과 HashTable의 차이는 뭘까?
1. 동기화
- Hashtable은 동기화되어 Thread-safe 합니다. 즉, 멀티스레드 환경에서 한 번에 하나의 스레드만 Hashtable에 변경을 가할 수 있습니다.
- 반면에, HashMap은 비동기화되어 있어 Thread-safe 하지 않습니다. 이로 인해 HashMap이 Hashtable보다 빠르며, 동시성을 요구하지 않는 경우에는 HashMap이 더 적합합니다.
2. NULL 허용 여부
- Null Key 및 Null Value: HashMap은 하나의 Null Key와 여러 개의 Null Value를 허용합니다. 반면에 Hashtable은 Null Key 또는 Null Value를 허용하지 않습니다.
import java.util.*;
public class Main {
public static void main(String[] args) {
// HashMap 예제
HashMap<Integer, String> hmap = new HashMap<Integer, String>();
hmap.put(1, "Apple");
hmap.put(null, "Orange"); // Null key를 허용
hmap.put(2, null); // Null value를 허용
System.out.println("HashMap: " + hmap);
// Hashtable 예제
Hashtable<Integer, String> htab = new Hashtable<Integer, String>();
htab.put(1, "Apple");
// htab.put(null, "Orange"); // Null key를 허용하지 않아, 이 코드는 에러를 발생시킴
// htab.put(2, null); // Null value를 허용하지 않아, 이 코드는 에러를 발생시킴
System.out.println("Hashtable: " + htab);
}
}
3. LinkedHashMap
💡 LinkedHashMap
- Map 인터페이스의 하나인 HashMap의 하위 클래스로, '키(key)'-'값(value)' 쌍을 해시맵에 저장하는 동시에 더블 링크드 리스트에도 입력 순서에 따라 저장합니다. 이로 인해 원소들의 삽입 순서를 기억하는 특징이 있습니다.
- 키와 값에 NULL을 허용하며 키는 중복되지 않습니다. 만약 동일한 키로 데이터를 저장하면, 기존 데이터를 덮어쓰게 됩니다.
- LinkedHashMap은 해시맵의 빠른 접근성을 유지하면서도 더블 링크드 리스트로 인해 입력 순서대로 데이터를 반복할 수 있는 기능을 제공합니다.
// LinkedHashMap 생성
LinkedHashMap<String, Integer> scores = new LinkedHashMap<String, Integer>();
// 값 추가
scores.put("David", 85);
scores.put("Jane", 95);
scores.put("Susan", 84);
scores.put("Brenda", 92);
// 값 출력 (삽입 순서대로 출력됨)
for(Map.Entry<String, Integer> entry : scores.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
System.out.println(key + " : " + value);
}
4) 문제로 확인하기
1. 프로그래머스 : 폰켓몬
💡 프로그래머스 : 폰켓몬
💡 문제 설명
- 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.
1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택
이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.
💡 제한사항
- nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
- nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
- 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
- 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.
💡 프로그래머스 : 폰켓몬 - 문제 풀이
- 해시 알고리즘의 Key, Value를 활용하여 쉽게 탐색을 수행합니다.
- 최대 가질 수 있는 폰켓몬의 종류를 구하기 위해서 hashMap의 put()를 이용하여 고유한 폰켓몬의 종류(key)와 폰켓몬의 개수(value)를 hashmap에 저장할 수 있습니다.
import java.util.*;
class Solution {
public int solution(int[] nums) {
int answer = 0;
// key(폰켓몬 번호), value(폰켓몬 번호 별 개수)
Map<Integer, Integer> resultMap = new HashMap<>();
// 폰켓몬 번호 별 개수를 Map 요소 값에 추가합니다.
for (int num : nums) {
resultMap.put(num, resultMap.containsKey(num) ? resultMap.get(num) + 1 : 1);
}
// 폰켓몬의 종류 별 개수
answer = resultMap.size();
// 최대로 얻을수 있는 폰켓몬 개수
int obtainCnt = Math.abs(nums.length / 2);
// 폰켓몬의 종류 보다 얻을 수 있는 개수가 많은 경우 폰켓몬 종류 반환
// 폰켓몬의 종류 보다 얻을 수 있는 개수가 적은 경우 얻을 수 있는 개수 반환
return answer < obtainCnt ? answer : obtainCnt;
}
}
2. 프로그래머스 : 완주하지 못한 선수
💡 프로그래머스 : 완주하지 못한 선수
💡 문제 설명
- 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
💡 제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
💡 프로그래머스 : 완주하지 못한 선수 - 문제 풀이
- 해시 알고리즘의 Key, Value 값을 최대한 활용하여 탐색을 수행합니다.
1. Map 내에 참가자 목록(participant)을 추가합니다. 참가자 이름(key), 참가여부 체크(value) - 0: 참가, 1: 미 참가
2. 완주 한 인원을 체크 Key 값에 따라 업데이트 수행, 참가여부에 따라 참가여부 체크(value)를 -1로 참가 체크를 수행합니다.
3. Map을 순회하면서 0이 아닌 값을 찾아서 결과로 반환합니다. 값이 0이 아니면 미 참가로 간주하고 key 값을 반환합니다.
import java.util.*;
class Solution {
public String solution(String[] participant, String[] completion) {
String answer = "";
Map<String, Integer> pHashMap = new HashMap<>();
// Map 내에 참가자 목록(participant)을 추가합니다. 참가자 이름(key), 참가여부 체크(value) - 0: 참가, 1: 미 참가
for (String participantItem : participant) {
pHashMap.put(participantItem, pHashMap.getOrDefault(participantItem, 0) + 1);
}
// 완주 한 인원을 체크 Key 값에 따라 업데이트 수행, 참가여부에 따라 참가여부 체크(value)를 -1로 참가 체크를 수행합니다.
for (String completionItem : completion) {
pHashMap.put(completionItem, pHashMap.get(completionItem) - 1);
}
// Map을 순회하면서 0이 아닌 값을 찾아서 결과로 반환합니다.
for (Map.Entry<String, Integer> entry : pHashMap.entrySet()) {
if (entry.getValue() != 0) {
answer = entry.getKey();
}
}
return answer;
}
}
[ 더 알아보기 ]
💡getOrDefault(Object key, V defaultValue)
- Map 내에 key 값이 존재하는지 여부를 체크하여, 존재하지 않는 경우 defaultValue 값을 반환합니다. 존재하는 경우 본래의 value 값을 반환합니다.
Map<String, Integer> fruitMap = new HashMap<>();
fruitMap.put("바나나", 10);
// "사과"라는 키가 없으므로, 기본값인 0을 반환
int appleCount = fruitMap.getOrDefault("사과", 0);
System.out.println(appleCount); // 출력: 0
오늘도 감사합니다. 😀
반응형
'Java > 알고리즘 & 자료구조' 카테고리의 다른 글
[Java/알고리즘] 탐색 알고리즘 : 해시 알고리즘(Hash Algorithm) 이해하기 -2 : 문제로 이해하기 (0) | 2024.05.27 |
---|---|
[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -2: 문제로 이해하기 (1) | 2024.01.21 |
[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -1 : 종류, 활용방안 (1) | 2024.01.09 |
[Java/알고리즘] 정렬 알고리즘(Sort Algorithm) 이해하기 -1 : 기본 구조 및 종류 (1) | 2023.12.02 |
[Java/알고리즘] 깊이 우선 탐색(DFS) / 너비 우선 탐색(BFS) 이해하기 -1 : 이론 및 구조 (3) | 2023.11.26 |