Java공부(코딩)

코딩초보의 자바(Java)공부 29일차 - { Set }

동곤일상 2025. 1. 15. 12:43
반응형
전에 계속
Hash 에 대해 배우고
HashSet도 구현해서 만들어봤죠?
이번에는 자바에서 제공하는 컬렉션프레임워크Set에
대해서 알아보겠습니다.


자바가 제공하는 HashSet , LinkedHashSet

 

set자료구조

set은 순서가없으며 중복을 허용하지않음


 

컬렉션프레임워크 - Set

**Collection 인터페이스**

`Collection` 인터페이스는 `java.util` 패키지의 컬렉션 프레임워크의 핵심 인터페이스 하나이다. 인터페이

스는 자바에서 다양한 컬렉션, 데이터 그룹을 다루기 위한 메서드를 정의한다. `Collection` 인터페이스는 `List` ,

`Set` , `Queue` 같은 다양한 하위 인터페이스와 함께 사용되며, 이를 통해 데이터를 리스트, 세트, 등의 형태로

리할 있다. 

 

Set인터페이스의 주요메서드

 


1. HashSet

**구현:** 해시 자료 구조를 사용해서 요소를 저장한다.

**순서:** 요소들은 특정한 순서 없이 저장된다. , 요소를 추가한 순서를 보장하지 않는다.

**시간 복잡도:** `HashSet` 주요 연산(추가, 삭제, 검색) 평균적으로 `O(1)` 시간 복잡도를 가진다.

**용도:** 데이터의 유일성만 중요하고, 순서가 중요하지 않은 경우에 적합하다.

 

앞에 글에서 우리가 구현한 MyHashSetV3가 HashSet과 같음.!!


2. LinkedHashSet

**구현:** `LinkedHashSet` `HashSet` 연결 리스트를 추가해서 요소들의 순서를 유지한다.

 

**순서:** 요소들은 추가된 순서대로 유지된다. , 순서대로 조회 요소들이 추가된 순서대로 반환된다.

 

**시간 복잡도:**

LinkedHashSet``HashSet` 마찬가지로 주요 연산에 대해 평균 `O(1)` 시간 복잡도 가진다.

 

**용도:** 데이터의 유일성과 함께 삽입 순서를 유지해야 적합하다.

 

**참고**: 연결 링크를 유지해야 하기 때문에 `HashSet` 보다는 조금 무겁다.

 


자바가 제공하는 Set2 - TreeSet

3. TreeSet

**구현:** `TreeSet` 이진 탐색 트리를 개선한 레드-블랙 트리를 내부에서 사용한다.

**순서:** 요소들은 정렬된 순서로 저장된다.

순서의 기준은 비교자(`Comparator` ) 변경할 있다. 비교자는 뒤에서 다룬다.

**시간 복잡도:** 주요 연산들은 `O(log n)` 시간 복잡도 가진다. 따라서 `HashSet` 보다는 느리다.

**용도:** 데이터들을 정렬된 순서로 유지하면서 집합의 특성을 유지해야 사용한다. 예를 들어, 범위 검색이나

정렬된 데이터가 필요한 경우에 유용하다. 참고로 입력된 순서가 아니라 데이터 값의 순서이다. 예를 들어 3, 1, 2

순서대로 입력해도 1, 2, 3 순서로 출력된.

 

트리구조 복습

 

부모노드와 자식노드로 구성 됨.

가장 높은 조상을 루트(root) 한다.

자식이 2개까지 있는 트리를 **이진 트리** 한다.

여기에 노드의 왼쪽 자손은 작은 값을 가지고, 오른쪽 자손은 값을 가지는 것을 **이진 탐색 트리** 한다.`

TreeSet` 이진 탐색 트리를 개선한 레드-블랙 트리를 사용한다.

.기본개념은 비슷하므로 알아보자

 

 

**이진 탐색 트리 - 순회**

이진 탐색 트리의 핵심은 입력 순서가 아니라, 데이터의 값을 기준으로 정렬해서 보관한다는 점이다.

따라서 정렬된 순서로 데이터를 차례로 조회할 있다. (순회 있다.)

데이터를 차례로 순회하려면 중위 순회라는 방법을 사용하면 된다. 왼쪽 서브트리를 방문한 다음, 현재 노드를

리하고, 마지막으로 오른쪽 서브트리를 방문한다. 방식은 이진 탐색 트리의 특성상, 노드를 오름차순(숫자가

커짐)으로 방문한다.

 

중위순회 순서

쉽게 이야기해서 자신의 왼쪽의 모든 노드를 처리하고, 자신의 노드를 처리하고, 자신의 오른쪽 모든 노드를 처리하는

방식이다.

10 기준에서 왼쪽 서브트리를 방문한다.

5 기준에서 왼쪽 서브트리를 방문한다.

**1 출력**한다.

**5 자신을 출력**한다.

5 기준으로 오른쪽 서브트리를 방문한다.

**6 출력**한다.

**10 자신을 출력**한다.

10 기준에서 오른쪽 서브트리를 방문한다.

15 기준에서 왼쪽 서브트리를 방문한다.

**11 출력**한다.

**15 자신을 출력**한다.

15 기준으로 오른쪽 서브트리를 방문한다.

**16 출력**한다.

 

순서대로 1, 5, 6, 10, 11, 15, 16 출력된 것을 확인

 


자바가 제공하는 Set 예제

package collection.set;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;

public class JavaSetMain {

	public static void main(String[] args) {
		run(new HashSet<>());
		run(new LinkedHashSet<>());
		run(new TreeSet<>());

	}

	private static void run(Set<String> set) {
		System.out.println("set.getClass : "+set.getClass());
		set.add("1");
		set.add("A");
		set.add("3");
		set.add("B");
		set.add("C");
		set.add("2");
		
		Iterator<String> iterator = set.iterator();
		while(iterator.hasNext()) {
			System.out.print(iterator.next()+" ");
		}
		System.out.println();
	}

}

set.getClass : class java.util.HashSet

1 A B 2 3 C

set.getClass : class java.util.LinkedHashSet

1 A 3 B C 2

set.getClass : class java.util.TreeSet

1 2 3 A B C

 

`HashSet` : 입력한 순서를 보장하지 않는다.

`LinkedHashSet` : 입력한 순서를 정확히 보장한다.

`TreeSet` : 데이터 값을 기준으로 정렬한다.

 

 

`iterator()` 호출하면 컬렉션을 반복해서 출력할 있다.

`iterator.hasNext()` : 다음 데이터가 있는지 확인한다.


자바가 제공하는 Set4 - 최적화

 

**정리**

실무에서는 `Set` 필요한 경우 `HashSet` 가장 많이 사용한다. 그리고 입력 순서 유지, 정렬의 필요에 따라서

`LinkedHashSet` , `TreeSet` 선택하면 된다.

 


문제와 풀이1

문제1 - 중복 제거

**문제 설명**

여러 정수가 입력된다. 여기서 중복 값을 제거하고 값을 출력해라.

30, 20, 20, 10, 10 출력되면 중복을 제거하고 출력하면 된다. 출력 순서는 관계없다.

출력 ): 30, 20, 10 또는 10, 20, 30 또는 20, 10, 30등과 같이 출력 순서는 관계 없다.

 

package collection.set.ex;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class SetEx1 {
//30, 20, 20, 10, 10이 출력되면 중복을 제거하고 출력하면 된다. 출력 순서는 관계없다.
	public static void main(String[] args) {
		HashSet<Integer> hashSet = new HashSet<>();
		Scanner scanner = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<>();
		int a =1;
		System.out.println("숫자를 입력(0입력시 종료 or 15개입력시 종료)");
		while(a!=0) {
			a = scanner.nextInt();
			hashSet.add(a);	
			list.add(a);
		}
		
		System.out.println("입력 데이터 : "+list);
		System.out.println("순서를 보장하지 않으며 \n"
				+ "중복을 허용하지 않는 컬렉션프레임워크만들기");
		System.out.println(hashSet);
		
		

	}

}

숫자를 입력(0입력시 종료 or 15개입력시 종료)

12

12

145

50

40

40

100

100

90

0

입력 데이터 : [12, 12, 145, 50, 40, 40, 100, 100, 90]

순서를 보장하지 않으며

중복을 허용하지 않는 컬렉션프레임워크만들기

[145, 50, 100, 40, 90, 12]


문제2 - 중복 제거와 입력 순서 유지

**문제 설명**

여러 정수가 입력된다. 여기서 중복 값을 제거하고 값을 출력해라.

30, 20, 20, 10, 10 출력되면 중복을 제거하고 출력하면 된다.

**입력 순서대로 출력**해라.

출력 ): 30, 20, 10

 

 

정답

입력한순서대로 출력해야하니

위에 코드에서

HashSet -->LinkedHashSet

package collection.set.ex;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Scanner;

public class SetEx2 {
//30, 20, 20, 10, 10이 출력되면 중복을 제거하고 출력하면 된다. 출력 순서는 관계없다.
	public static void main(String[] args) {
		HashSet<Integer> hashSet = new LinkedHashSet<>();
		Scanner scanner = new Scanner(System.in);
		ArrayList<Integer> list = new ArrayList<>();
		int a =0;
		System.out.println("숫자를 입력(0입력시 종료 or 15개입력시 종료)");
		while(true) {
			a = scanner.nextInt();
			if(a==0) {
				break;
			}
			else {
			hashSet.add(a);	
			list.add(a);}
		}
		
		System.out.println("입력 데이터 : "+list);
		System.out.println("순서를 보장하고 \n"
				+ "중복을 허용하지 않는 컬렉션프레임워크만들기");
		System.out.println(hashSet);
		for (Integer i : hashSet) {
			System.out.print(i+" ");
			
		}
	}

}

숫자를 입력(0입력시 종료 or 15개입력시 종료)

30

20

10

10

40

40

50

9

8

0

입력 데이터 : [30, 20, 10, 10, 40, 40, 50, 9, 8]

순서를 보장하고

중복을 허용하지 않는 컬렉션프레임워크만들기

[30, 20, 10, 40, 50, 9, 8]

30 20 10 40 50 9 8


문제와 풀이2

문제4 - 합집합, 교집합, 차집합

**문제 설명**

숫자의 집합이 제공된다.

집합1: `1, 2, 3, 4, 5`

집합2: `3, 4, 5, 6, 7`

집합의 합집합, 교집합, 차집합을 구해라. 출력 순서는 관계없다.

합집합: 집합의 합이다. 참고로 중복은 제거한다. `[1, 2, 3, 4, 5, 6, 7]`

교집합: 집합의 공통 값이다. 참고로 중복은 제거한다. `[3, 4, 5]`

차집합: 집합1에서 집합2 같은 값을 나머지 `[1, 2]`

다음 실행 결과를 참고하자.

`Set` 인터페이스의 주요 메서드를 참고하자.

package javaBasic2.collection.set.ex;

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

public class Ex3 {
	public static void main(String[] args) {
		Set<Integer> set1 = new HashSet<>(List.of(1, 2, 3, 4, 5));
		Set<Integer> set2 = new HashSet<>(List.of(3, 4, 5, 6, 7));

		Set<Integer>union = new HashSet<Integer>(set1);
		union.addAll(set2);
		

		Set<Integer> intercection = new HashSet<Integer>(set1);
		intercection.retainAll(set2);
	

		Set<Integer> diffrence = new HashSet<Integer>(set1);
		diffrence.removeAll(set2);

		System.out.println("합집합(addAll 사용) : "+union);
		System.out.println("교집합(retainAll 사용) : "+intercection);
		System.out.println("차집합(removeAll 사용) : "+diffrence);

	}

}

합집합 : [1, 2, 3, 4, 5, 6, 7]

교집합 : [3, 4, 5]

차집합 : [1, 2]

 


문제5 - Equals, HashCode
문제 설명
RectangleTest , 실행 결과를 참고해서 다음 Rectangle 클래스를 완성하자.
Rectangle 클래스는 width , height 가 모두 같으면 같은 값으로 정의한다

package javaBasic2.collection.set.ex;

import java.util.Objects;

public class Rectangle {
	private int width;
	private int height;
	
	public Rectangle(int width ,int height) {
		this.width = width;
		this.height = height;
	}
	

	@Override
	public String toString() {
		return "Rectangle [width=" + width + ", height=" + height + "]";
	}


	@Override
	public int hashCode() {
		return Objects.hash(height, width);
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Rectangle other = (Rectangle) obj;
		return height == other.height && width == other.width;
	}
	
	

}
package javaBasic2.collection.set.ex;

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

public class RectangleMain {

	public static void main(String[] args) {
		Set<Rectangle> set = new HashSet<Rectangle>();
		
		set.add(new Rectangle(10, 20)); 
		set.add(new Rectangle(10, 20)); //똑같은것이라 판단하고 셋에 넣지않음!
		set.add(new Rectangle(20, 20)); 
		
		System.out.println("set : "+set+"\n");
		for (Rectangle r : set) {
			System.out.println(r+" ");
			
		}
		

	}

}

set : [Rectangle [width=20, height=20], Rectangle [width=10, height=20]]

 

Rectangle [width=20, height=20]

Rectangle [width=10, height=20]