[알고리즘 개념] Map, Set, Queue
HashMap
- HashMap는 해싱을 기본으로 데이터를 저장한다. HashMap에는 (Key,Value) 형태로 데이터가 저장된다.
- HashMap은 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부
- HashMap는 TreeMap과는 다르게 데이터의 순서는 고려하지 않는다.
<HashMap에서 자주 이용되는 코드>
1. HashMap 선언하기
HashMap<Key의 자료형, value의 자료형> hashmap이름 = new HashMap<>();
2.HashMap에 데이터 넣기
m.put(Key, Value)
3.HashMap에 있는 데이터 제거하기
m.remove(Key)
4.HashMap에서 특정 key의 value값 받기
m.get(Key)
5. 특정 key가 HashMap에 존재하는지 확인하기
m.containsKey(Key)
6.특정 key가 존재하면 그 value값을 받고, 아니면 정해둔 값 입력받기
m.getOrDefault(Key, 존재x이면 반환하는 값)
TreeMap
TreeMap는 HashMap과 다르게 균형잡힌 이진트리로 데이터를 저장한다. 때문에 TreeMap에서 저장, 삭제등을 하려면 시간복잡도는 O(logN)입니다.
1. 선언방법
TreeMap<key자료형, value자료형> treemap명 = new TreeMap<>();
<TreeMap에서 자주 이용되는 코드>
1. TreeMap 선언하기
HashMap<Key의 자료형, value의 자료형> hashmap이름 = new HashMap<>();
2. TreeMap에 데이터 넣기
m.put(Key, Value)
3. TreeMap에 있는 데이터 제거하기
m.remove(Key)
4. TreeMap에서 특정 key의 value값 받기
m.get(Key)
5. 특정 key가 TreeMap에 존재하는지 확인하기
m.containsKey(Key)
6.특정 key가 존재하면 그 value값을 받고, 아니면 정해둔 값 입력받기
m.getOrDefault(Key, 존재x이면 반환하는 값)
7. TreeMap 순회하기
Java에서는 vector, stack등의 컨테이너들을 iterator라는 반복자를 이용해 순회가 가능하다
iterator 참고
https://ethereal-coder.tistory.com/151
[알고리즘 개념] iterator
iterator이란?ArrayList, Stack, Queue, Deque 등과 같이 Colletion이 정의되어 있는 자료구조들을 컨테이너라고 부른다. 이 컨테이너 내에 있는 원소들을 순회하기 위해 사용하는 것이 iterator이다. 예를 들어,
ethereal-coder.tistory.com
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
TreeMap<Integer, Integer> t = new TreeMap<>();
t.put(1, 2);
t.put(3, 4);
t.put(5, 6);
// Iterator선언
Iterator<Entry<Integer, Integer>> it = t.entrySet().iterator();
// key 기준 오름차순으로 순회
while(it.hasNext()) {
Entry<Integer, Integer> entry = it.next();
System.out.println(entry.getKey() + " " + entry.getValue());
}
}
}여기서 entry는 key와 value를 출력하기 위한 함수입니다.
위와 같이 하면 key값이 오름차순으로 정렬된 상태로 출력되게 key와 value가 출력됩니다.
Entry는 import java.util.Map.Entry; 를 꼭 해줘야 한다.
HashSet
- HashSet는 해싱을 기본으로 데이터를 저장한다
- HashSet은 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부
- HashSet는 TreeSet과는 다르게 데이터의 순서는 고려하지 않는다.
- Set는 Map와 다르게 단일 데이터만 저장한다(key,value X)
<HashSet에서 자주 이용되는 코드>
1.HashSet 선언하기
HashSet<데이터의 자료형> HashSet명 = new HashSet<>();2. HashSet에 데이터 넣기
s.add(데이터)
3. HashSet에 있는 데이터 제거하기
s.remove(데이터)
4.HashSet에 해당 데이터 있는지 확인하기
s.contains(데이터)TreeSet
HashSet와 다르게 균형잡힌 이진트리로 데이터를 저장한다.
<TreeSet에서 자주 이용되는 코드>
1.TreeSet 선언하기
TreeSet<T> s = new TreeSet<>();2. TreeSet에 데이터 넣기
s.add(데이터)
3. TreeSet에 있는 데이터 제거하기
s.remove(데이터)
4.TreeSet에 해당 데이터 있는지 확인하기
s.contains(데이터)
5. 특정 수보다 같거나 큰/ 작은 값중 가장 가까이 있는 값
s.ceiling(E) // 크거나 같은
s.floor(E) // 작거나 같은
없으면 Null을 반환한다.
6. 특정 수보다 큰/작은 값 중 가장 가까이 있는 값
s.higher(E) // 큰
s.lower(E) // 작은없으면 Null을 반환한다.
7.가장 작은/큰 숫자 반환하기
s.first() //가장 작은 값
s.last() //가장 큰 값
PreorityQueue
Queue는 가잠 먼저 온 값이 먼저 나오는 선입선출 방식이다.
PreorityQueue는 이와 달리 Queue내에 있는 값 중 가장 작은 값을 반환한다.
<PreorityQueue에서 자주 이용되는 코드>
1.PreorityQueue 선언하기
PriorityQueue<자료형> pq = new PriorityQueue<>();
2.PreorityQueue에 데이터 저장하기
pq.add(데이터)
3.PreorityQueue 데이터 삭제하기
pq.remove(데이터)
4.PreorityQueue가 비었는지 확인하기
pq.isEmpty()
5.PreorityQueue에서 가장 작은 데이터 확인하기
pq.peek()
6.PreorityQueue에서 가장 작은 데이터 내보내기
pq.poll()
출처
https://www.codetree.ai/missions/8/problems/hashmap-basic/introduction