Java Collection Framework - Collection interface - Set

안녕하세요.

 

오늘은 이전 포스팅에 있어 Set 자료구조에 대해 알아보도록 하겠습니다. 

 

Set Interface는 아래와 같은 특징을 가지고 있습니다.

• 데이터의 중복을 허용하지 않으며 순서를 유지하지 않음.
• 순서가 존재하지 않기 때문에 Index로 접근이 불가능함.
• 중복이 불가능하기 때문에 null 또한, 한 개만 저장할 수 있음. 

 

그럼 HashSet에 대해 알아보도록 하겠습니다.

HashSet는 아래와 같은 특징을 가지고 있습니다.

• 배열과 연결 노드를 연결한 자료구조
• 임의 검색 접근 속도에서는 가장 빠른 속도를 보임.
• 추가, 삭제, 검색 등의 접근성이 매우 뛰어남.
• 순서가 보장되지 않아 순서 예측은 불가능. 

Set<Integer> hashSet = new HashSet<>();

hashSet.add(70);
hashSet.add(20);
hashSet.add(90);
hashSet.add(20); // 중복

hashSet.size(); // 3 - 중복 카운트 X

hashSet.toString(); // [20, 90, 70]

 

만약, 순서를 유지하는 Set 자료 구조가 필요하다면 어떻게 해야 할까요?

즉, 순서 유지는 필요하지만 중복을 제거하고 싶다면 LinkedHashSet를 사용하면 됩니다

• 순서를 가지는 Set 자료구조
• 추가된 순서 또는 가장 최근에 접근한 순서대로 접근이 가능함
• 중복은 제거하며 순서를 유지하고 싶을 때 적합

Set<Integer> linkedHashSet = new LinkedHashSet<>();

linkedHashSet.add(70);
linkedHashSet.add(20);
linkedHashSet.add(80);
linkedHashSet.add(20); // 중복 추가

linkedHashSet.size(); // 3 - 중복 카운트 X

linkedHashSet.toString(); // [70, 20, 80] 입력 순서 유지

 

그럼, 데이터를 정렬하며 중복을 허용하지 않을 때는 어떤 자료구조를 사용하면 될까요? 

TreeSet 자료를 사용하시면 되는데요.

TreeSet은 이진 검색 트리 자료구조를 기반으로 데이터를 저장합니다.

이를 통해 데이터를 정렬하고 범위 검색, 정렬, 검색 등에서 높은 성능을 보장한다는 것이 특징이며 Set을 기반으로 하고 있기 때문에 중복을 허용하지 않는 특징을 가지게 됩니다.  

Set<Integer> treeSet = new TreeSet<>();

treeSet.add(5);
treeSet.add(3);
treeSet.add(4);
treeSet.add(1);
treeSet.add(2);

treeSet.toString(); // [1, 2, 3, 4, 5]

 

그럼 문제를 풀어보도록 하겠습니다. 

 

해당 문제들이 어떤 자료구조에 적합한지 결정해 볼까요.

 

1. 중복을 허용하지 않는다. (y / n)

2. 순서가 중요하다.  (y / n)

3. 정렬이 되어 있어야 한다. (y / n)

 

백준 3052 나머지 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class BOJ_3052 {
    /*
     * 10개를 입력받은 뒤, 이를 42로 나눈 나머지를 구한다. 그 다음 서로 다른 값이 몇 개 있는지 출력하는 프로그램을 작성하시오.
     * 1. 중복을 허용하지 않는다. (y / n) => Y(서로 다른 값) 
     * 2. 순서가 중요하다.  (y / n) => N (순서가 중요하지 않음, 크기가 중요함)
     * 3. 정렬이 되어 있어야 한다. (y / n) => N (정렬이 중요하지 않음, 크기가 중요함)
     * 
     * 단순 Set 자료로 해결이 가능하기에 HashSet을 통해 문제를 해결 가능함.
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
        Set<Integer> set = new HashSet<>();

        for (int i = 0; i < 10; i++) {
            int temp = Integer.parseInt(br.readLine()) % 42;
            set.add(temp);
        }
        System.out.println(set.size());
    }
    
}

 

백준 13414 수강신청

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.StringTokenizer;

public class BOJ_13414{
        /*
     * 순서에 따라 정렬해야함. + 중복 발생하면 안된다. 
     * 
     * 1. 중복을 허용하지 않는다. (y / n) => Y(같은 값이 있으면 삭제 후 다시 삽입) 
     * 2. 순서가 중요하다.  (y / n) => Y (수강 신청 시간 )
     * 3. 정렬이 되어 있어야 한다. (y / n) => N 
     * 
     * 단순 Set 자료로 해결이 가능하기에 HashSet을 통해 문제를 해결 가능함.
     */
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
		int k = Integer.parseInt(st.nextToken());
        int l = Integer.parseInt(st.nextToken());
		LinkedHashSet<String> hs = new LinkedHashSet<>();
		String tmp;

		for(int i=0;i<l;i++){
			tmp = br.readLine();
			if(hs.contains(tmp)) hs.remove(tmp);
			hs.add(tmp);
		}
		Iterator<String> it = hs.iterator();
		while(it.hasNext()){
            sb.append(it.next() + "\n");
            if(--k < 1) break;
		}

        System.out.println(sb.toString());
		
		
	}
}

 

백준 2957

 

위 문제는 TreeSet을 이용하여 풀 수 있습니다. 

해당 문제까지 풀어보시길 추천 드립니다.