[Java] 배열의 유사도 (HashSet과 HashMap의 차이)

Problem 💻

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

문제 설명

두 배열이 얼마나 유사한지 확인해보려고 합니다. 문자열 배열 s1과 s2가 주어질 때 같은 원소의 개수를 return하도록 solution 함수를 완성해주세요.

---

제한사항

• 1 ≤ s1, s2의 길이 ≤ 100
• 1 ≤ s1, s2의 원소의 길이 ≤ 10
• s1과 s2의 원소는 알파벳 소문자로만 이루어져 있습니다
• s1과 s2는 각각 중복된 원소를 갖지 않습니다.

---

입출력 예: s1s2

result

["a", "b", "c"]	["com", "b", "d", "p", "c"]	2
["n", "omg"]	["m", "dot"]	0

---

---

Approach 1 ❌ - 나의 초기 접근법

1. 각 배열의 요소들을 하나씩 검토해야 한다. - for문을 이용해서 인덱스0부터 차례대로 요소를 꺼내서 출력시킨다.

2. 인덱스 순서에 상관없이 상대 배열의 요소와 비교를 시켜야 한다. 같은지 찾는 문법을 모른다.

3. 같은 요소의 개수를 세야 한다. - 요소를 세는 문법이 떠오르지 않는다 

---

Approach 2 ⭕ - 나의 접근법에 대한 교정

1. 문제 이해

- 문자열 배열 s1과 s2가 주어진다.

- 두 배열에 공통으로 존재하는 문자열의 개수를 찾아야 한다.

 

1. 배열의 요소를 하나씩 검토해야 한다.
for 문을 이용해 배열의 인덱스 0부터 끝까지 반복하며 모든 요소를 출력하거나 사용할 것을 생각했었다.
이는 기본적인 접근법이다. 배열의 모든 요소를 순회해야 하기 때문에 반드시 필요한 과정이다.

2. 인덱스 순서에 상관없이 상대 배열의 요소와 비교한다.
배열 간의 비교를 위해 인덱스 순서를 무시하고 요소만 비교해야 한다는 점을 정확히 이해했었다.
하지만 배열에는 contains() 같은 편리한 메서드가 있다는걸 몰랐기 때문에 이렇게 생각한거다.

3. 같은 요소의 개수를 세야 한다.
공통 요소를 찾고 이를 카운트해야 한다는 목표를 명확히 설정했다.
“요소를 세는 문법”이 떠오르지 않는다는 점에서 필요한 도구나 메서드에 대한 지식이 부족했음을 인지했다.
-----
평가
1. 논리적 흐름: 문제를 이해하고 나름의 해결 전략을 세우는 과정은 논리적이었다
모든 요소를 순회하고, 공통 요소를 확인하며, 이를 카운트하는 단계적 접근은 옳았다.
배열의 한계를 이해하고 필요한 메서드가 없다는 점을 인식한 것도 괜찮았다.
2. 한계: 배열의 기본적인 한계를 넘어서 효율적인 해결 방식을 찾는 데 있어 어려움을 겪고 있었다.
• 배열을 Set으로 변환하거나, contains()를 직접 구현하는 등의 방법을 고려하지 못했다.

----
개선할 점과 방법
1. 효율성에 대한 고려
• 배열로 직접 비교하면 각 요소마다 다른 배열을 반복 비교해야 하므로 시간 복잡도가 O(n * m)이다.
• 이를 개선하려면 배열을 Set으로 변환해야 한다. Set은 요소의 포함 여부를 평균 O(1)의 시간 복잡도로 확인할 수 있다.
• 개선 방법:

Set<String> set = new HashSet<>(Arrays.asList(s2));​

2. 모르는 문법과 메서드 탐구
• 배열과 관련된 자바 라이브러리 메서드(Arrays, Set, HashSet)를 학습하면 문제 해결에 필요한 도구를 더 잘 활용할 수 있다.
• 추천 학습 항목:
  -  Arrays.asList()를 이용한 배열을 리스트로 변환
  - HashSet과 같은 컬렉션 활용법
  - Set.contains() 메서드 사용법
3. 논리 단순화
• 배열을 단순히 for 문으로 순회하고 또 다른 for 문을 돌려 비교하면 코드가 복잡해질 수 있다.
• Set을 활용하면 공통 요소 탐색이 간결해진다.
• 개선된 코드:

Set<String> set = new HashSet<>(Arrays.asList(s2));
long count = Arrays.stream(s1).filter(set::contains).count();​

 

2. 풀이 논리

  2.1 배열 순회 : 두 배열의 모든 요소를 검토하기. 예를 들어, 배열 s1의 각 요소를 꺼내면서 s2의 요소들과 비교한다.

  2.2 효율적인 비교 : 배열을 순회하며 요소를 비교할 때, 배열보다 Set 자료 구조를 활용하면 더 효율적으로 요소의 포함 여부를 확인할 수 있다. 

  2.3 공통 요소 카운트 : 공통 요소를 확인할 때마다 카운트를 증가시킨다. 

---

Solution 💡

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

public class CommonElements {
  public static int solution(String[] s1, String[] s2) {
     //s2를 Set으로 변환 (빠른 포함 여부 확인)
     Set<String> set = new HashSet<>();
     for (String elelment : s2) {
         set.add(element);
     }
     
     // s1의 각 요소가 s2(Set)에 포함되어 있는지 확인
     int count = 0;
     for (String element : s1) {
         if (set.contains(element)) {
             count++;
             }
     }
     return count;
}

public static void main(String[] args) {
     // 테스트 예제
     String[] s1 = {"a", "b", "c"};
     String[] s2 = {"com", "b", "d", "p", "c"};
     System.out.println(solution(s1, s2)); // 출력: 2
  }
}

 

 

단계별 논리적 사고 과정
1. 문제 분해
  - 배열을 비교하고 공통 요소를 확인한 뒤, 카운드해야 한다는 문제를 세단계로 나눈다:
   1. 배열 순회
   2. 공통 요소 확인
   3. 카운트

2. 효율성 고려
  - 반복문만 사용하는 대신, 효율적인 자료구조인 Set을 활용한다.

3. 구현 단계
  - 작은 기능부터 하나씩 추가한다. 
     1. Set으로 변환.
     2. contains()로 공통 요소 확인.
     3. 카운트 증가. 

 

1. Set으로 변환

Set<String> set = new HashSet<>();
for (String element : s2) {
    set.add(element);
}

- 배열 s2를 HashSet으로 변환한다.

- Set은 중복을 허용하지 않고, 포함 여부를 빠르게 확인할 수 있는 자료구조이다.

 

2. 포함 여부 확인

for (String element : s1) {
    if (set.contains(element)) {
        count++;
    }
}

- s1의 각 요소를 set.contains()로 확인한다.

- 공통 요소가 있으면 count를 증가시킨다. 

 

3. 시간 복잡도

• s2를 Set으로 변환하는 데 O(m)

• s1을 순회하며 포함 여부를 확인하는 데 O(n)

• 전체 시간 복잡도: O(n + m)

---

Reference 📄

 

HashSet과 HashMap

 

1 . HashSet이란?

HashSet은 중복을 허용하지 않는 집합(Set)이다.

내부적으로 HashMap을 이용해서 데이터를 관리하지만, 키(key)만 사용하고 값(value)은 없다.

쉽게 말해, HashSet은 "데이터의 존재 여부만 확인하는 "데 최적화된 자료구조이다. 

 

2. HashSet의 특징

 2.1 중복 허용 안 함

     - 같은 데이터를 두 번 넣으면 하나만 저장된다.

Set<String> set = new HashSet<>();
set.add("a");
set.add("a");
System.out.println(set.size()); //출력: 1 (중복 제거됨)

 

set.size()는 HashSet이나 다른 Set 인터페이스를 구현한 자료구조에서 사용되는 메서드로, Set에 저장된 요소의 개수를 반환한다.
• size()는 O(1)의 시간 복잡도를 가지므로 매우 빠르게 동작한다.

 

  2.2 순서가 없음 

    - 저장된 데이터의 순서를 보장하지 않는다.

set.add("b");
set.add("c");
System.out.println(set); // 출력: [a, c, b] (순서 보장 안 됨)

 

 

  2.3. 포함 여부 확인

set.contains(element) 메서드를 통해 특정 데이터가 있는지 빠르게 확인할 수 있다.

내부적으로는 해싱(hash)을 사용하여 데이터를 검색한다.

 

3. HashSet과 HashMap의 차이

 

예시로 차이 이해하기

HashSet

Set<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
System.out.println(set.contains("apple")); //true
System.out.println(set.contains("orange")); //false

데이터가 "존재하는지"만 확인 가능하다.

 

HashMap

Map<String, String> map = new HashMap<>();
map.put("apple", "fruit");
map.put"carrot", "vegetable");
System.out.println(map.get("apple")); // fruit
System.out.println(map.containsKey("carrot")); // true

Key와 Value의 짝을 저장한다. - HashMap이 Key와 Value를 저장하는 원리는 밑에 ...

 

4. HashSet에서 contains()가 작동하는 방식

set.contains(element) 메서드는 다음과 같은 원리로 작동한다:

1. 해싱(Hashing)

• HashSet 내부에서 저장된 요소는 해시값(고유 숫자 값)으로 관리된다.

• 특정 요소를 찾을 때도 동일한 해시값을 계산하여 저장된 해시값과 비교한다.

• 해싱 덕분에 포함 여부를 확인하는 속도가 매우 빠르다.

2. 시간 복잡도

set.contains(element)의 평균 시간 복잡도는 O(1)이다.

이는 해시값을 기반으로 즉시 확인하기 때문이다.

 

Set<String> set = new HashSet<>();
set.add("a");
set.add("b");
set.add("c");

// "b"가 있는지 확인
if (set.contains("b")) {
    System.out.println("b는 HashSet에 포함되어 있습니다.");
} else {
    System.out.println("b는 HashSet에 포함되어 있지 않습니다.");
}

 

5.. HashSet을 사용하는 이유

• 빠른 검색 속도: 포함 여부 확인이 빠르며, 반복문에서 사용하기 적합하다.

• 중복 제거: 중복된 데이터를 자동으로 제거한다.

• 이 문제에서는 HashSet을 사용해 s2 배열을 변환한 후, s1의 요소와 비교하는 방식으로 공통 요소를 빠르게 찾을 수 있었다.

 

HashSet이 왜 필요한가?
1. 효율적: 배열로 직접 비교하려면 중첩 반복문으로 인해 시간이 오래 걸린다.
2. 간단한 코드: contains() 메서드로 포함 여부를 쉽게 확인할 수 있다.
3. 중복 제거: 자동으로 중복을 제거해 데이터의 유효성을 유지할 수 있다.

 

---

해싱(Hashing)이란?

해싱은 데이터를 고유한 숫자 값(해시값)으로 변환하는 기술이다.

이 고유한 숫자 값을 사용하여 데이터를 빠르게 검색, 삽입, 삭제할 수 있도록 한다.

 

해싱은 주로 HashMap, HashSet, HashTable과 같은 자료구조에서 사용되며, 데이터 검색을 빠르게 하기 위한 핵심 기술이다.

 

해싱의 원리

1. 입력 데이터 → 해시 함수 → 해시

   데이터를 해시 함수(Hash Function)에 입력하면 고유한 해시값(Hash Value)이 생성된다.

   예: "apple" → hash("apple") → 42

2. 해시값을 사용해 저장 위치 결정

   해시값은 보통 배열의 인덱스로 사용되거나 데이터의 저장 위치를 계산하는 데 사용된다

   예: "apple"은 해시값 42를 얻고, 배열의 42번 위치에 저장된다.

3. 검색 시에도 해시 함수 활용

  특정 데이터를 검색할 때도 해시 함수를 사용하여 해당 데이터의 위치를 바로 찾아낸다.

  예: "apple"을 검색하면 hash("apple") → 42로 계산하고, 42번 위치를 확인한다.

 

 

해싱이 중요한 이유

해싱은 다음과 같은 이유로 효율적이다:

1. 빠른 데이터 검색

  • 일반적으로 배열이나 리스트에서 데이터를 검색하려면 요소를 하나씩 확인해야 하므로 O(n)의 시간이 걸린다.

     반면 해싱을 사용하면 데이터의 위치를 해시값으로 계산해 바로 접근하므로, 평균 O(1)의 시간 복잡도를 가진다.

2. 효율적인 데이터 저장

• 데이터가 고유한 위치(해시값)로 저장되므로, 중복 데이터를 제거하거나 고유한 데이터만 유지하기 쉬워진다.

 

 

해시 함수란?

해시 함수(Hash Function)는 입력 데이터를 특정 규칙에 따라 고유한 숫자(해시값)로 변환하는 함수이다.

 

좋은 해시 함수의 조건:

1. 빠른 계산: 입력 데이터에서 해시값을 빠르게 계산할 수 있어야 한다.

2. 고유성: 서로 다른 데이터는 다른 해시값을 가져야 한다.

3. 균등 분포: 해시값이 가능한 한 고르게 분포되어야 한다. (한 위치에 데이터가 몰리지 않도록)

 

 

해싱의 문제점: 충돌(Hash Collision)

충돌이란 서로 다른 데이터가 같은 해시값을 가지는 경우를 말한다.

예:

• "apple" → 해시값 42

• "banana" → 해시값 42

 

충돌은 해시 함수가 완벽하지 않기 때문에 발생할 수 있으며, 이를 처리하기 위한 다양한 방법이 있다.

 

 

충돌 해결 방법

1. 체이닝(Chaining)

   동일한 해시값의 데이터를 연결 리스트로 관리한다.

   예: 배열의 42번 위치에 "apple"과 "banana"가 모두 저장되지만, 연결 리스트로 이어 붙인다.

2. 오픈 어드레싱(Open Addressing)

   충돌이 발생하면 다음 빈 공간(배열의 다른 위치)을 찾아 데이터를 저장한다.

   예: 42번이 충돌되면 43번에 데이터를 저장한다.

 

 

HashSet에서 해싱의 역할

• HashSet은 해싱을 사용하여 데이터를 저장하고 관리한다.

• 요소를 추가하거나 검색할 때, 해시 함수를 사용하여 빠르게 데이터의 위치를 계산하고 포함 여부를 확인한다.

• 예: set.contains("apple")는 "apple"의 해시값을 계산하고, 해당 위치에 데이터가 있는지 확인한다.

 

 

해싱의 사용 예시

 

1. HashSet

Set<String> set = new HashSet<>();
set.add("apple"); // "apple"의 해시값을 계산하여 저장
set.add("banana");

System.out.println(set.contains("apple")); // 해시값을 계산하여 존재 여부 확인

 

 

2. HashMap

Map<String, Integer> map = new HashMap<>();
map.put("apple", 5); // "apple"의 해시값을 계산해 저장
map.put("banana", 3);

System.out.println(map.get("apple")); // 해시값을 계산하여 "apple"의 값(5)을 반환

 

 

 

정리

1. 해싱의 정의
  • 데이터를 고유한 숫자(해시값)로 변환하여 빠르게 저장/검색할 수 있게 하는 기술.
2. HashSet과 해싱
  • 데이터의 중복 제거와 포함 여부 확인을 빠르게 처리할 수 있다.
  • set.contains()는 해싱을 사용해 평균 O(1)로 동작한다.
3. HashMap과 해싱
  • 데이터를 키-값 쌍으로 관리하며, 해시값을 사용해 키의 위치를 계산한다.
4. 해싱의 이점
  • 빠른 데이터 접근(O(1) 복잡도)
  • 효율적인 데이터 저장 및 검색

 

 

---

HashMap에서 Key와 Value가 어떻게 짝을 이루어 저장되고, 이를 어떻게 검색하는지. 

 

HashMap은 해싱(Hashing) 기술을 사용해 Key를 기반으로 Value를 저장하는 자료구조이다.

Key는 고유한 식별자 역할을 하고, Value는 Key와 연결된 데이터이다.

 

HashMap의 동작 과정

1. Key의 해시값 계산

  • map.put(Key, Value)를 호출하면, HashMap은 먼저 Key에 대해  해시 함수(Hash Function)를 호출하여 해시값(Hash Code)을 계산한다.

  • 예를 들어, "apple"의 해시값이 42라고 가정한다.

2. 저장 위치 결정

  • 계산된 해시값을 기반으로 데이터를 저장할 배열의 인덱스를 결정한다.

  • 예를 들어, 해시값 42를 배열의 42번 위치로 매핑한다.

3. Key-Value 쌍 저장

  • 결정된 위치에 Key와 Value를 함께 저장한다.

  • 예를 들어, "apple"과 "fruit"를 배열의 42번 위치에 저장한다.

4. 검색 시에도 같은 과정 반복

  • map.get(Key)를 호출하면 HashMap은 Key의 해시값을 계산하고, 해당 위치에서 Key를 찾아 Value를 반환한다

 

코드 예제의 작동 원리

Map<String, String> map = new HashMap<>();
map.put("apple", "fruit");
map.put("carrot", "vegetable");

System.out.println(map.get("apple")); // 출력: fruit
System.out.println(map.containKey("carrot")); //출력: true

작동 과정 상세 설명

1. Key “apple”과 Value “fruit” 저장

   map.put("apple", "fruit")가 호출되면:

      1. "apple"의 해시값을 계산한다.

      2. 계산된 해시값을 기반으로 배열의 특정 위치를 찾는다.

      3. 배열의 해당 위치에 "apple"과 "fruit"를 Key-Value 쌍으로 저장한다.

• 예를 들어, 해시값 42 → 배열의 42번 위치에 저장된다.

 

2. Key “carrot”과 Value “vegetable” 저장

    map.put("carrot", "vegetable")가 호출되면:

     1. "carrot"의 해시값을 계산한다.

     2. 계산된 해시값을 기반으로 배열의 또 다른 위치를 찾는다.

     3. 배열의 해당 위치에 "carrot"과 "vegetable"를 Key-Value 쌍으로 저장한다.

     • 예를 들어, 해시값 53 → 배열의 53번 위치에 저장된다.

 

3. Value 검색: map.get(“apple”)

   map.get("apple")이 호출되면:

     1. "apple"의 해시값을 다시 계산한다.

     2. 해당 해시값을 기반으로 배열의 위치(예: 42번)를 찾는다.

     3. 배열의 42번 위치에서 Key "apple"과 연결된 Value "fruit"를 반환한다.

 

4. Key 존재 여부 확인: map.containsKey(“carrot”)

   map.containsKey("carrot")가 호출되면:

     1. "carrot"의 해시값을 계산한다.

     2. 해당 해시값을 기반으로 배열의 위치(예: 53번)를 찾는다.

     3. 배열의 53번 위치에서 Key "carrot"이 존재하는지 확인한다.

     4. Key가 존재하므로 true를 반환한다.

 

 

HashMap의 내부 구조

HashMap은 내부적으로 배열 + 연결 리스트 또는 배열 + 트리를 사용하여 데이터를 저장한다.

1. 배열(Bucket)

  • 데이터를 저장할 기본 구조이다.

  • 해시값에 따라 Key-Value 쌍이 저장된다.

2. 연결 리스트(Linked List)

  • 해시값이 같은 Key가 여러 개 있는 경우, 충돌이 발생한다.

  • 이때, 충돌된 Key-Value 쌍을 연결 리스트로 저장한다.

3. 트리 구조(Tree)

  • 데이터가 많아지면 연결 리스트 대신 트리 구조를 사용하여 검색 속도를 유지한다.

 

 

HashMap의 장점

1. 빠른 데이터 검색

   • 해시값을 사용해 배열 인덱스를 계산하므로, 데이터 검색 속도가 평균적으로 O(1)이다.

2. Key-Value 관계 관리

   • Key를 통해 관련된 Value를 빠르게 조회할 수 있다.

3. 유연한 Key

   • Key로 문자열, 숫자, 객체 등 다양한 자료형을 사용할 수 있다.

 

 

HashMap의 주의점

1. Key는 고유해야 함

• Key는 중복될 수 없으며, 중복된 Key를 넣으면 기존 Value가 덮어씌워진다.

map.put("apple", "fruit");
map.put("apple", "snack");
System.out.println(map.get("apple")); // 출력: snack (덮어씌워짐)

 

2. 해시 충돌

• 서로 다른 Key가 같은 해시값을 가질 경우 충돌이 발생한다.

• HashMap은 연결 리스트나 트리를 사용해 충돌을 해결한다.

 

요약
• HashMap의 원리
Key의 해시값을 계산하여 저장 위치를 찾고, Key와 Value를 배열에 함께 저장하며, 검색 시에도 동일한 방식으로 Value를 반환한다.
• 주요 메서드
  - put(Key, Value): Key-Value 쌍을 저장한다.
  - get(Key): Key에 해당하는 Value를 반환한다.
  - containsKey(Key): Key가 존재하는지 확인한다.