오늘의 학습 키워드 및 문제
#해시 #HashSet
백준 브론즈3) 아 맞다 마늘
문제풀이
문제에서 중복이 없고, 포함되지 않은 재료를 찾아야 한다고 하니 set이 바로 생각났다.
- 재료의 개수를 입력받음
- 레시피의 재료와 실제 넣은 재료를 각각 입력받음
- 실제 넣은 재료를 HashSet에 저장
- 반복문으로 HashSet에 레시피의 재료가 있는지 확인
4-1. 레시피의 재료가 없다고 하면 해당 재료를 빼먹은 것이므로 출력 후 return
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashSet<String> hs = new HashSet<>();
int n = Integer.parseInt(br.readLine());
String[] ingredient = br.readLine().split(" ");
String[] realIngredient = br.readLine().split(" ");
for(int i=0; i<n-1; i++) {
hs.add(realIngredient[i]);
}
for(int i=0; i<n; i++) {
if (!hs.contains(ingredient[i])) {
System.out.println(ingredient[i]);
br.close();
return;
}
}
br.close();
}
}다른방법
1. List 사용
문제를 풀고나니 막상 중복된 데이터도 없으니 꼭 HashSet으로 안풀어도 될 것 같아서 List로도 풀어봤다.
그런데 HashSet보다 메모리를 더 사용했고 시간도 더 오래걸렸다. 왜일까? (아래에 내용이..)
[HashSet] : 14588KB 112ms
[ArrayList] : 14652KB 132ms
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
List<String> ingredient = new ArrayList<>(Arrays.asList(br.readLine().split(" ")));
List<String> realIngredient = new ArrayList<>(Arrays.asList(br.readLine().split(" ")));
for(int i=0; i<n; i++) {
if(!realIngredient.contains(ingredient.get(i))) {
System.out.println(ingredient.get(i));
br.close();
return;
}
}
br.close();
}
}2. contains() 대신 remove() 사용
remove()는 HashSet에 지정한 요소가 있으면 제거하고 true를 반환한다.
넣은 재료를 삭제함으로써 탐색을 최적화 할 수 있다.
시간이 더 적게 드는 것을 확인할 수 있었다. 이정도 차이는 미미한가..
[contains()] : 14588KB 112ms
[remove()] : 14608KB 108ms
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
HashSet<String> hs = new HashSet<>();
int n = Integer.parseInt(br.readLine());
String[] ingredient = br.readLine().split(" ");
String[] realIngredient = br.readLine().split(" ");
for(int i=0; i<n-1; i++) {
hs.add(realIngredient[i]);
}
for(int i=0; i<n; i++) {
if (!hs.remove(ingredient[i])) {
System.out.println(ingredient[i]);
br.close();
return;
}
}
br.close();
}
}공부한 내용정리
- Set은 중복된 값을 저장하지 않고 순서가 없으며 영어 대소문자를 구분
HashSet VS ArrayList
✒️ HashSet과 ArrayList의 주요 차이
HashSet
- 해시 테이블을 사용하여 데이터를 저장
- 검색, 삽입, 삭제의 평균 시간복잡도 O(1)
- 중복 허용X, 순서X
ArrayList
- 내부적으로 배열을 사용하여 데이터를 저장
- 삽입의 평균 시간복잡도는 O(1) 배열 크기 확장이 필요한 경우엔 O(n)
- 검색, 삭제의 평균 시간복잡도는 O(n)
✒️ 메모리와 속도 차이
메모리 차이
- HashSet은 고유 값만 저장하고 해시 테이블로 관리하여 추가적인 메모리가 필요하지만 검색 속도 향상으로 메모리 효율이 상대적으로 높음.
- ArrayList는 모든 데이터를 순서대로 저장하고 검색 시 리스트 전체를 순회하기 때문에 더 많은 메모리를 소비할 가능성 있음. 중복 데이터가 있을 경우 메모리 낭비 더 심함.
속도 차이
- HashSet의 contains는 O(1) 이지만 ArrayList의 contains는 O(n) 이므로 데이터의 크기가 커질 수록 속도 차이 벌어짐.
✒️ 왜 HashSet의 contains는 O(1) 이지만 ArrayList의 contains는 O(n) 인가요?
HashSet의 검색 과정
- contains를 호출하면 검색할 데이터의 hashCode()를 계산하고 해당 버킷(bucket)으로 직접 접근
- 동일한 버킷(bucket) 충돌로 인해 여러 데이터가 저장될 수 있지만 equals를 통해 데이터가 일치하는지 확인
- 충돌이 적은 경우 O(1)에 가까운 성능을 보임
ArrayList의 검색 과정
- contains를 호출하면 맨 처음부터 끝까지 각 원소를 순회하며 equals 메서드를 호출해 데이터가 일치하는지 확인
- n개의 원소가 있다면 최악의 경우 n번의 비교가 필요하기에 O(n)의 성능을 가짐
✒️ 그래도 이해가 안되네요. 예를 들어서 설명해주시겠어요?
- HashSet: 도서관에서 특정 책을 찾을 때, 책에 고유한 바코드가 있어 바코드를 스캔하면 바로 책의 위치를 알 수 있는 경우.
- ArrayList: 도서관에서 특정 책을 찾을 때, 책 제목을 하나씩 확인하면서 원하는 책을 찾는 경우.
Please, Steadily