🔗 문제
난이도 - 실버 4
알고리즘 분류 - 자료 구조, 정렬, 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵
💬 풀이
집합 연산에 관한 문제로, A집합과 B집합의 차집합(A-B)을 계산하고 원소의 개수와 그 값을 출력하는 단순 수학 문제이다. 하지만 풀이 시에 시간초과의 이슈로 쉽게 풀리지는 않는 문제이다.
또한, 집합의 원소로 받을 수 있는 수의 범위에 집중해야 하는데 2,147,483,647 이하(= int의 범위)의 자연수라는 조건이 있어 최소 int형 이상의 자료형으로 선언해야 함을 알 수 있다.
첫 번째 시도
단순하게 A집합과 B집합을 int형 배열로 선언하고 이중 for문을 돌며 두 원소가 같은지 판별 후, 같지 않은 경우에만 A집합의 원소를 결과 리스트에 추가하는 방식으로 구현했다.
하지만 이 방식은 자바의 집합 자료구조를 전혀 사용하지 않고 단순 구현한 것이기에 당연히 시간 초과 문제로 실패했다.
두 번째 시도
Java에서 기본 Set의 자료형과 같은 역할의 HashSet으로 Aset을 구성하고 B를 입력받음과 동시에 차집합 연산을 하는 방식으로 구현하였다. 이는 테스트 코드 실행 시에 전부 정상적으로 답이 나왔지만 왜인지 자꾸 실패로 떴다.
세 번째 시도
위 코드에서 HashSet을 TreeSet으로만 바꾸어주었다.
두 자료형 클래스의 차이는 아래에 적어두겠다.
💻 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class _1822 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
TreeSet<Integer> Aset = new TreeSet<>();
st = new StringTokenizer(br.readLine());
for (int i=0; i<A; i++) {
Aset.add(Integer.parseInt(st.nextToken()));
}
st = new StringTokenizer(br.readLine());
for (int j=0; j<B; j++) {
int Bnum = Integer.parseInt(st.nextToken());
Aset.remove(Bnum);
}
sb.append(Aset.size()+"\n");
for (Integer num : Aset) {
sb.append(num+ " ");
}
System.out.println(sb);
}
}
📊 정리
TreeSet VS HashSet
Java의 Collections 프레임워크 내에 있는 Set 인터페이스에는 집합에 관한 자료형 클래스들이 존재한다. 간단하게 해당 클래스에 대한 설명을 덧붙이고자 한다.
HashSet
가장 기본적인 Set 컬렉션의 클래스로, 자료가 추가된 순서와 상관없이 출력되며 중복을 허용하지 않는다. 이는 Hash 기능과 Set 컬렉션이 합쳐진 형태이므로 삽입, 삭제, 조회의 성능이 매우 뛰어나다.
주로 아이디 중복 확인 등과 같이 빠르게 데이터를 찾는 경우 등 해시에 의한 빠른 색인으로 활용될 수 있다.
TreeSet
이진 검색 트리를 활용하여 자료 정렬 → 프로그래머가 직접 ‘어떤 기준으로 값의 크기를 비교할 것인지’ 구현해야 함
중복되지 않으면서 특정 규칙에 의해 정렬된 집합 형태를 쓰고 싶은 경우에 사용
LinkedHashSet
*Set 중에 순서를 보장하는 유일한 클래스이다. 하지만 데이터 중복이 허용되지 않는 점은 동일하다.
HashSet의 Link의 특징이 더해져 자연스럽게 순서가 보장된다. 즉, 중복은 허용하지 않으면서 순서를 보장받고 싶은 경우에 사용한다.
📍 어려웠거나 해결하지 못한 부분
- TreeSet과 HashSet의 차이점을 파악하고 속도의 측면에서 TreeSet이 더 적합하다고 판단은 했으나, 왜 HashSet을 사용했을 때 시간초과가 아닌 단순 실패로만 떴는지 궁금하긴 하다.
📍 참고 자료
