프로그래머스 데브코스를 위한 코테 Java로 풀이 하는것을 위한 페이지입니다.
데브 코스 지원 후 다시 Python으로 변경할 것이며, 여러 방법으로 코테 푸는 것이 도움이 될 거라 생각하여 Java 문법도 정리할 예정입니다.
기초
기본 베이스
public class Solution{
public static void main(String args[]){
// 내용 작성
}
}
// boolean 형식
boolean flag = true;
flag = false;
// 기본형 타입 Primitive type
// 변수 Type 및 자료형 크기
// 정수형
byte; // 1 byte
short;// 2 byte
int; // 4 byte
long l = 70000000L; // 8 byte
System.out.println(Long.BYTES+ " --> " + Long.SIZE + "\t" + Long.MIN_VALUE + "~" + Long.MAX_VALUE); //바이트 크기, 비트 크기, 최대 값(최소값은 MIN)
// 실수형
float f = 9.8F; // 4 byte
double; // 8 byte
// 문자형
char c = 'a'; // 2 byte
// 논리형
boolean b = true; // 1 byte, true, false
// 위 출력문으로 여러가지 바이트, 비트, 최대 값을 구할 수 있음.
// 자료형 별 작성법(Byte, Short, Integer, Long, (int)Character
// 참조형 타입(Reference Data Type)
// Class, Array, Interface, String/immutable 등
// 데이터가 저장된 메모리의 주소 값을 저장하는 변수
int a = 12345;
String str = "12345";
a.length() // Err
str.length() // 5
// 자료형 변환 조심
double d = 100 / 3;
System.out.print(d); // 33.0
double d = 100 / (double)3; // 둘 중 하나 형 변환 해야함
System.out.print(d); // 33.3333
입력(Scanner)
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
Scanner sc = new Scanner(System.in);
int a = sc.nextInt();
int b = sc.nextInt();
String a = sc.next();
sc.close();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int num = Integer.parseInt(st.nextToken());출력
System.out.print();
System.out.println();
// %d, %f, %c, %s, %b(부울), %n(줄바꿈), %e(지수), %o(8진수), %x(16진수)
System.out.printf("%d %.2f %b", n, f, bool);
// 문자 + 숫자 출력 주의
int b = 12345;
System.out.print(b + 1); // 12346
System.out.print("답 : " + b + 1); // 답 : 123451
System.out.print("답 : " + (b + 1)); // 답 : 12346
//BufferedReader br;
System.out.print(br.readLine().replaceAll(" ", ""));
StringBuilder sb = new StringBuilder();
for(int value : numbers) {
sb.append(value).append('\n');
}
System.out.println(sb);조건
if(){}
else if(){}
else{}
switch(case){ case 0: xx; break; }
int answer = num < 2 ? num : 2;반복문
for(int i=0; i<10; i++){}
while(i<10){}
// 향상된 for 문
String[] names = {"leo", "bum"};
for(String name : names) System.out.print(name);문자
Character.isUpperCase(c); // true, false
Character.toUpperCase(c); // 소 -> 대 반환
Character.isLowerCase(c); // true, false
Character.toLowerCase(c); // 대 -> 소 반환
// Character -> Integer
char n = '4';
int a = Character.getNumericValue(n);
// ASCII
String a = "Apple";
char c = a.charAt(0); // 'A'
System.out.print((char)(c+32)); // 출력: a
String wordString = "showVideo";
char[] words = wordString.toCharArray();문자열
String str1 = String.format("a = %d", a)
// 문자열 이어 붙이기
String answer = "";
for(int i = 65;i<92;i++) answer += String.valueOf((char)i);
// 문자열 반복
String str = "solution";
for(int i = 0; i < str.length(); i++){
System.out.println(str.substring(0, i));
System.out.print(str.charAt(i));
System.out.println(str.substring(i+1));
}
str.length() // 문자열의 길이 length랑 다름.
// 문자열 붙이기
String conStr = str.concat(str1);
String joinStr = String.join("",str,str1);
// Integer -> 문자열 변환
int a = 12345;
String stra = String.valueOf(a); // "12345" 저장
System.out.print(stra.length()); // 5
// 문자열 -> 숫자 변환
int b = Integer.valueOf(stra); // 12345 저장
// 문자열 -> 문자 반복
for(Character c : a.toCharArray()) System.out.print(c);
// 문자열 대소문자
str.toUpperCase(); // 일시적 반환 str = str.toUpperCase();
str.toLowerCase(); // 일시적으로 반환
// 문자열 포함 여부
str.contains("111");
// 문자열 비교
String str = "abc";
String str2 = "abc";
str.equals("enter");
str.equals(str2);
// 문자열 분리 ([1,2,3,4] -> 1234)
String string = "[1,2,3,4]";
StringTokenizer st = new StringTokenizer(string, "[],");
// 정규식
String[] s1 = string.split("[\\[\\]\\,]"); // 해당 경우 s1[0] = "", s1[1] = "1", ... , s1[4] = "4" 형태
string[] s2 = string.split("[^0-9]");
String subS = string.subString(1, s.length - 1);
String[] s1 = subS.split(",");
// StringBuffer
StringBuffer sb = new StringBuffer();
sb.append('s');
sb.append('h');
sb.append("ow");
System.out.println(sb.toString());
배열
변수 타입에 따라 다르게 지정해야 합니다.
import java.util.*;
import java.util.Arrays;
int[] answer = {};
int[] answer = new int[arr.length];
answer.length; // 길이 문자열의 length()랑 다름.
String[] participant = {"leo", "bum"};
Arrays.sort(participant);Math
Integer num = 55;
int max = Math.max(3, 5);
int min = Math.min(3, 5);
int numSqrt = (int)Math.sqrt(num); // 출력 결과: 7
int power = (int)Math.power(2, 10); // 2^10정렬(Sort)
// 배열 정렬
// dual-pivot Quicksort, 평귱 O(nlogn) 최악 O(N²)
Arrays.sort(nums, 0, 4); // index 0 ~ 3 요소만 정렬
// ArrayList 등 정렬
// Timsort -> 합병 및 삽입정렬 알고리즘
// hybrid sorting algorithm라고도 불림
// 합병정렬 -> 최선, 최악 O(nlogn)
// 삽입정렬 -> 최선 O(n), 최악O(N²)
// 합병의 최악 + 삽입의 최선을 합친 Timesort는 O(N) ~ O(nlogn) 보장
Collections.sort(nums)
// Class 변수내 비교
// x를 순서대로 정렬
// x가 같다면 y를 순서대로 정렬
Collections.sort(list, Comparator.comparingInt((Point p) -> p.x)
.thenComparingInt(p -> p.y));
Collections.sort(list, new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
if(o1.y == o2.y) return o1.x - o2.x;
return o1.y - o2.y;
}
});
// 문자열 사전순 정렬
String str1 = "Java";
String str2 = new String("Java");
String str3 = "java";
ArrayList<String> list = new ArrayList<>();
list.addAll("Java", "java");
System.out.println(str1.compareTo(str2));
System.out.println(str2.compareTo(str3));
Collections.sort(list, (o1, o2) -> o1.compareTo(o2));
✔ 내림차순 정렬
// 문자열
Arrays.sort(arr, Collections.reverseOrder());
// int Type
int[] arr = {4,3,2,1,5};
Integer[] arr3 = Arrays.stream(arr).boxed().toArray(Integer[]::new);
Arrays.sort(arr3, Collections.reverseOrder());중급, 고급
- 해당 카테고리는 작성자 수준이 달라지면서 위치도 달라질 예정
Arrays
import java.util.Arrays;
// 오름차순 정렬
int[] nums = {3,4,5,2,1};
String arr[] = {"apple","orange","banana","pear","peach","melon"};
Arrays.sort(nums); // 1, 2, 3, 4, 5
Arrays.sort(arr); // apple, banana, melon, orange, peach, pear
// 내림차순 정렬
Arrays.sort(nums, Collections.reverseOrder()); // int는 안됨. Integer 객체만 가능
// 일부분만 정렬
Arrays.sort(nums, 0, 4); // index 0 ~ 3 요소만 정렬
// 객체 배열 정렬(특정 위치로 정렬)
// Comparable인터페이스의 compareTo() 메서드를 구현 <이름, 나이>에서 나이로 정렬하는 예제
class People implements Comparable{
private String name;
private int age;
// 생성자 메서드
@Override
public int compareTo(People people){
if(this.age < people.age){
return -1;
}else if(this.age == people.age){
return 0;
}else{
return 1;
}
}
}
People[] arr = { new People("상현", 20)
, new People("철수", 14)
, new People("경완", 31)
, new People("대호", 40)
, new People("지운", 24)
};
Arrays.sort(arr);
Arrays.sort(arr, Collections.reverseOrder());
// 배열 복사
int[] temp = Arrays.copyOfRange(array, 2, 5); // 복사할 배열, 시작 Index, 끝 Index
ArrayList
import java.util.*; // 또는
import java.util.ArrayList;
// 선언
ArrayList list1 = new ArrayList(); // Tpye 미설정시 Object로 선언
List<Integer> list = new ArrayList<Integer>();
List<Integer> num = new ArrayList<>(20); // 초기 용량(capacity) 지정
List<Integer> num2 = new ArrayList<>(Arrays.asList(1,2,3)); // 생성시 값 추가
List<Student> members = new ArrayList<>();
if(!list.contains(nums[i])){
list.add(nums[i]);
}
// ArrayList 추가
list.add(3);
list.add(null); // null값도 add 가능
list.add(1, 10); // index 1 위취에 10 삽입
members.add(new Student("홍길동", 15)); // 생성자로 넣기 또는 위에서 선언한 객체 넣기
// 삭제
list.remove(1);
list.clear();
// 값 변경
list.set(index, value);
// ArrayList 검색
list.contains(3); // true false
list.indexOf(2); // 2가 존재하는 index 반환 없으면 -1
list.isEmpty();
// ArrayList size
list.size();
// List 붙이기
ArrayList<String> listOne = new ArrayList<>();
ArrayList<String> listTwo = new ArrayList<>();
listOne.addAll(listTwo);
// 출력
System.out.println(list.get(0)); // 0번째 index 출력
Iterator it = list.iterator(); //Iterator 선언
LinkedList
import java.util.*;
// 선언
LinkedList list = new LinkedList();
LinkedList<Integer> num = new LinkedList<Integer>();
// 추가
list.addFirst(10);
list.addLast(20);
list.add(30); // inedx 생략 시 가장 마지막에 데이터 추가
list.add(1, 15);
// 삭제
list.removeFirst();
list.removeLast();
list.remove(); // 생략 시 0 번째 index 제거
list.remove(1); // index 1 제거
list.clear();
// size
list.size();
// 출력
for(Integer i : list){
System.out.println(i);
}
Iterator<Integer> iter = list.iterator();
while(iter.hasNext()){
System.out.println(iter.next());
}
// 검색
list.contains(1); // true false 반환
list.indexOf(1); // 1이 있는 index 반환, 없으면 -1HashSet
import java.util.HashSet;
// HashSet 선언
HashSet<Integer> numberSet = new HashSet<>();
HashSet<Integer> set1 = new HashSet<Integer>(numberSet); // numberSet 값 복사
HashSet<Integer> set2 = new HashSet<Integer>(10, 0.7f); // 초기 capacity, load factor 지정 (초기 용량만 지정 가능)
HashSet<Integer> set3 = new HashSet<Integer>(Arrays.asList(1,2,3)); // 초기값 지정
// HashSet 삽입
numberSet.add(Integer.valueOf(comb));
numberSet.add(2);
// 삭제
numberSet.remove(2);
numberSet.clear();
// Iterator
numberSet.iterator();
// size() collection framework에서 사용
numberSet.size();
// 검색
set.contains(2);HashMap
HashMap은 저장공간보다 값이 추가로 들어오면 저장 공간을 약 2배로 늘린다. 따라서 초기 지정한 Map의 데이터 개수를 알고 있다면 초기 용량을 지정하는것이 좋다.
import java.util.HashMap;
// 키, 값 유형에 대한 선언은 int같은 기본 형태로 하면 오류가 나온다.
Map<String, String> pt = new HashMap<>();
HashMap<String, Integer> hm = new HashMap<>();
HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
HashMap<String, Integer> mp = new HashMap<>();
// key, value 값 넣기
hm.put("name", 3);
hm.putIfAbsent(name, 222); // 값이 존재하지 않는 경우에만 추가
// value 값 찾기
hm.get("name");
hm.getOrDefault("name", 0); // 최신 문법임. if(hm.get(name) == null)로 해결 가능
// map 길이
hm.size();
// String key를 Char 단위로 탐색
for(char c : key.toCharArray()){}
// key 제거
hm.remove(name);
hm.clear(); // 모든 값 제거
// 존재 여부
hm.containsKey(name);
hm.containsValue(5); // 내부 탐색 시간
hm.isEmpty();
// value 교체
hm.replace(name, 7); // 존재하는 경우에만 key를 변경
// key Set 반환
hm.keySet();
// value Collection 반환 (반환 Type이 Collection<Value>)
hm.values();
// 출력 keySet() 활용
for(Integer i : hm.ketSet()){
System.out.println("[Key]:" + i + " [Value]:" + hm.get(i));
}
// 출력 entrySet() 활용 (많은 데이터를 가져와야 한다면 entrySet()이 더 좋음)
for(Entry<String, Integer> entry : hm.entrySet()){
System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
// Iterator
Iterator<Entry<Integer, String>> entries = mp.entrySet().itreator();
while(entries.hasNext()){
Map.Entry<Integer, String> entry = entries.next();
System.out.println("[Key]:" + entry.getKey() + " [Value]:" + entry.getValue());
}
Iterator<Integer> keys = map.keySet().iterator();Iterator
import java.util.Iterator;
Iterator<Integer> it = hashSet.iterator();
// 아래 3가지 메소드
it.hasNext()
it.next()
it.remove()
while(it.hasNext()){
int number = it.next();
}
Exception
Exception
public int solution(int[] nums) throws Exception{
if (nums == null || nums.lenth == 0){
throw new Exception();
}
}
IOException
import java.io.IOException;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine()); // br.readLine()에서 IOException 발생
}NumberFormatException을 활용하여, 문자열이 숫자인지 아닌지 판단하는 함수
// 이 문자열이 숫자인지 아닌지 판단하는 함수
public static boolean isStringNumber(String s) {
try {
Double.parseDouble(s);
return true;
}
catch (NumberFormatException e) {
return false;
}
}람다(lambda)
Arrays.stream(arr).map(operand -> k % 2 == 0 ? operand + k : operand * k).toArray();
Collections.sort(list, Comparator.comparingInt((Point p) -> p.x).thenComparingInt(p -> p.y));Stack
Stack은 Java에서 지원하지만 직접 구현할 줄도 알아야한다. 해당 코드는 너무 길 수 있으므로 참고했던 블로그 링크를 남김. (https://go-coding.tistory.com/5)
후에 10828번 백준 문제에 대한 풀이와 함께 블로그에 작성할 예정
import java.util.Stack;
Stack<Integer> stack = new Stack<>();//push, pop, peek, empty, search 지원
for(int i=1; i<=5 ; i++) {
stack.push(i);
System.out.println(stack.peek());
} //1, 2, 3, 4, 5
stack.pop();
System.out.println("Pop()");
System.out.println(stack.peek()); //4 출력
System.out.println(stack.search(3)); //2 출력
System.out.println(stack.empty()); //false 출력Queue
Queue Interface를 구현하는 라이브러리는 크게 ArrayDeque, LinkedList, PriorityQueue가 있다.
보통 자바에서 사용은 Queue<Integer> q = new LinkedList<>();로 사용한다.
특정 상황시에 내부적으로 Array를 사용하거나 위 처럼 LinkedList로 구현한 큐가 있으며, 실제로 구현하는 코드는 후에 백준 18258과 함께 글을 남길 것이고, 해당에서는 만들어진 Class를 사용하는 방식으로 적을 것
Class 구현 공부는 다음 블로그를 참조했다.
https://st-lab.tistory.com/183
아래는 지원해주는 Queue<E> Interface다.
import java.util.LinkedList;
import java.util.Queue;
Queue<T> arraydeque = new ArrayDeque<>();
Queue<T> linkedlistdeque = new LinkedList<>();
Queue<T> priorityqueue = new PriorityQueue<>();
Queue<Integer> queue = new LinkedList<>(); //int형 queue 선언, linkedlist 이용
Queue<String> queue = new LinkedList<>(); //String형 queue 선언, linkedlist 이용
Queue<Integer> stack = new LinkedList<>(); //int형 queue 선언
// 추가
// add -> throw IllegalStateException | offer -> return null
queue.add(1); // queue에 값 1 추가
queue.add(2); // queue에 값 2 추가
queue.offer(3); // queue에 값 3 추가
// 삭제
// poll -> return null | remove -> throw Exception
queue.poll(); // 첫번째 값을 반환하고 제거 비어있다면 null
queue.remove(); // queue에 첫번째 값 제거
queue.clear(); // queue 초기화
// 첫 번째 값 탐색
queue.peek(); // queue의 첫번째 값 참조Deque
Deque에 선언된 대표적인 메소드
| Method | return | Description |
|---|---|---|
| add(E e) | boolean | 요소 추가, Queue가 Full인 경우 throw new IllegalStateException(); |
| offer(E e) | boolean | 요소 추가, Queue가 Full인 경우 return false |
| peek() | E | front 삭제 X 값 반환 |
| poll() | E | front 삭제 후 값 반환 |
| addLast(E e) | void | 요소 꼬리추가, Queue Full -> IllegalStateException |
| addFirst(E e) | void | 위와 동일 |
| offerLast(E e) | boolean | 요소 꼬리 추가 |
| offerFirst(E e) | boolean | 요소 헤드 추가 |
| peekFirst() | E | peek() |
| peekLast() | E | - |
| pollFirst() | E | poll() |
| pollLast() | E | - |
| size() | int | size() 반환 |
Deque<T> arraydeque = new ArrayDeque<>();
Deque<T> linkedlistdeque = new LinkedList<>();정규식
정규식에 대한 내용도 따로 언젠가는 다뤄보겠다. 우선 코드만 기록
// 숫자만 찾기
String numArr = "i213jhb5i23uh634";
numArr = numArr.replaceAll("[^0-9]", ""); //213523634이론
Array
- 같은 타입의 데이터들을 저장하는 자료 구조
- 연속된 메모리 공간에 데이터들을 저장
- 데이터들 각각은 이름은 없지만 Index로 접근 가능(offset 개념으로 사용)
2차원 배열
int[][] twoD = {{1, 2}, {3, 4}};
String[] names = {"easy", "code", "yeah"}; // 자바에서 String은 reference로 저장row - 행, 가로
col - 열, 세로
String[]은 각각의 reference 즉, 객체의 주소가 연속적으로 저장되는 것이고, 실제 저장된 객체의 String 값은 메모리의 연속적으로 저장되는 것이 아니다.
Memory 관점에서의 Array
연속된 메모리 공간에 데이터들을 저장하기 때문에 cpu cache를 통해 같은 배열에 있는 다른 데이터에 점근하는 시간을 단축할 수 있다.
Dynamic array(동적 배열)
- 크기가 변할 수 있는 array
- 데이터를 더하거나 빼는 것이 가능한 자료 구조
- resizable array, array list 등등으로 불림
동적으로 사이즈를 늘릴 때 더 큰 사이즈의 배열을 하나 만들고 거기에 복사한다.
이때 더 큰 사이즈의 경우 구현에 따라 사이즈를 다르게 늘릴 수 있다.
Associative array(연관 배열)
- key-value pair 들을 저장하는 ADT
- 같은 key를 가지는 pair는 최대 한 개만 존재
- map, dictionary라고 불리기도 함
List
- 값(value)들을 저장하는 추상자료형(ADT)
- 순서가 있음
- 중복을 허용
Set이나 Map을 사용하는게 더 적절한 상황이 아니라면, 거의 대부분 List를 사용
Array List
배열 Array를 활용하여 구현
삽입, 삭제 시 List의 이동 동작이 필요하여 O(N)의 시간 복잡도 필요
단, 접근에 대한 시간 복잡도는 O(1)
Linked List
Node를 연결(Linked) 시키는 형태로 구현
- head와 tail 존재
- Data와 Point(Reference)를 통해 하나의 Node 구성
삽입, 삭제 시 O(1)의 시간 복잡도 필요(단, 삽입과 삭제에 대한 위치를 찾는 시간 생각)
접근은 처음부터 해당 Node를 찾아야하기 때문에 최악에 경우 O(N) 소요
Linked List에 확장
1. circular linked list
가장 마지막 Node인 tail이 head를 가리키는 형태
2. Doubly linked list
Node에 Point가 prev와 next로 구성돼 앞과 뒤 모두 연결 가능
단, 메모리 효율 떨어지는 trade-off 현상
3. Circular doubly linked list
위 설명한 1,2 번을 합친 형태로 prev, next로 구성되있으며 tail -> head를 가리키는 형태
Array List vs Linked list
| Array List | Linked List | |
|---|---|---|
| 구현 | Array 사용 | Node 연결(linked) |
| 데이터 접근 시간 | 상수 시간 접근 | 위치에 따른 시간 |
| 삽입/삭제 시간 | 연산 후 데이터 시프트 추가 시간 | 연산을 위한 위치 이동 시간 |
| 리스트 크기 확장 | 배열 확장 필요한 경우 복사하는 추가 시간 | - |
| 검색 | 최악의 경우 리스트 아이템 수 확인 O(N) | 최악의 경우 리스트 아이템 수 확인 O(N) |
| CPU cache | CPU cache 이점 활용 | - |
| 구현 예 | Java의 ArrayList, CPython의 list | Java의 LinkedList |
근데 사실 Linked List는 대체 될 방법이 존재하여 대부분 Array List만 사용한다는 듯 하다. 나는 Coding Test 준비 중이니 Linked List 사용을 할 듯함.
Hash Table
- 검색하고자 하는 Key 값을 입력받아서
- 해시 함수를 통해 반환 받은 HashCode
- 배열의 Index로 환산해서
- Data로 접근하는 방식
Key 값은 String, 숫자형, FileData가 다 될 수 있다.
이때 만들어진 HashCode는 정수이며, index로 사용돼서 검색이 필요 없이 바로 접근 가능하다. O(1)
Hash Table(hash map)
- 배열과 해시 함수(hash function)를 사용하여 map을 구현한 자료 구조
- (일반적으로) 상수 시간으로 데이터에 접근하기 때문에 빠름
Hash Collision
- key는 다른데 hash가 같을 때
- key도 hash도 다른데 hash % map_capacity 결과가 같을 때
이런 경우 HashCollision이 발생하는데
해결 방법이 있다.
1. Open Addressing 방식
2. Separate Chaining 방식
Separate Chaining 방식
Array방에 중복해서 저장할 때 두 개의 key 값이 다르다면 Hash 충돌이 발생한 것.
Separate Chaining 방식은 해당 Node에 Linked된 Node를 연결시켜서 Data를 지키는 방식이다.
Open addressing
여기에는 세부적으로 또 여러 방식이 있다.
linear probing 방식이 존재하는데 해당 방식은 같은 배열 방에 Key가 존재한다면 Hash Collision이 발생한것이다.
이때 메모리의 빈 공간을 찾아서 해당 공간에 Key를 저장한다 함.
그렇다면 containsKey를 통해 Key를 찾으면 해당 Hash Index에 Key가 없을것이다.
그래서 다음 Memory에 Key가 존재하는지 확인하는 작업을 거친다 함.
(근데 그러면 효율이 떨어지지 않나? 싶은 생각이 듬)
만약 기존에 Hash Key값을 삭제한다면 deleted된 표시를 남긴다 함.
그렇게 Dummy Data를 넣어야 linear probing 방식으로 동작중이기 때문에 다른 Memory를 탐색하여 값이 존재하는지 확인할 수 있다함.
Hash table resizing
- 데이터가 많이 차게 되면 크기를 늘려줘야 한다.
CPython의 dictionary vs Java의 HashMap
| dictionary | HashMap | |
|---|---|---|
| 구현 | hash table 사용 | hash table 사용 |
| 데이터 접근 시간 | (보통) 모든 데이터를 상수 시간에 접근 | (보통) 모든 데이터를 상수 시간에 접근 |
| 삽입/삭제 시간 | (보통) 모든 데이터를 상수 시간에 접근 | (보통) 모든 데이터를 상수 시간에 접근 |
| 해시 충돌 해결 방법 | Open addressing | Separate chaining |
| default initial capacity | 8 | 16 |
| resize 타이밍 | map capacity의 2/3 이상 데이터 존재 시 | map capacity의 3/4 이상 데이터 존재 시 |
| resize 규모 | 4x or 2x | 2x |
| shrink 타이밍 | dummy 데이터 > 유효 데이터 일 때 | - |
| hash table capacity | power of 2 | power of 2 |
Map
- key-value pair 들을 저장하는 ADT
- 같은 key를 가지는 pair는 최대 한 개만 존재
- associative array, dictionary라고 불리기도 함
Map의 구현체
- hash table
- tree-based
Set
- 데이터를 저장하는 추상자료형(ADT)
- 순서를 보장하지 않음
- 데이터 중복을 허용하지 않음
- 데이터 조회(search)가 List보다 빠름
HashSet도 HashTable을 통해 구현한다.
실제로 Java에서 HashSet을 보면 HashMap을 통해 구현한다.
참고로 Python에서는 setentry라는 struct를 생성하여 key, hash값으로 set을 구현한다. dict로 구현하는것은 아님.
CPython의 set vs Java의 HashSet
| dictionary | HashMap | |
|---|---|---|
| 구현 | hash table 사용 | hash table 사용 |
| 데이터 접근 시간 | (보통) capacity와 상관없이 모든 데이터를 상수 시간에 빠르게 접근 | (보통) capacity와 상관없이 모든 데이터를 상수 시간에 빠르게 접근 |
| 해시 충돌 해결 방법 | Open addressing | Separate chaining |
| default initial capacity | 8 | 16 |
| resize 타이밍 | set capacity의 2/3 이상 데이터 존재 시 | set capacity의 3/4 이상 데이터 존재 시 |
| resize 규모 | 유효 데이터 수(c) > 50000 ? c X 2 : c X 4 | 2x |
| capacity 축소 가능성 | resize할 때 dummy data가 많다면, 새로운 capacity가 이전보다 작을 수 있음 | - |
| set capacity | power of 2 | power of 2 |
// names는 중복 X의 경우 Set vs List
for(String name: names){}list가 메모리도 적게 쓰고, 구현 특성 산 list가 단순하여 iteration이 더 빠름.
그래서 웬만하면 array list를 쓰는 것을 추천한다.
| List | Set | |
|---|---|---|
| 구현체 | Array List, Linked List | HashSet, LinkedHashSet, TreeSet |
| Memory | 덜 씀 | 더 씀 |
만약 자바의 경우 Linked Hash Set같은 경우 입력한 순서대로 저장
TreeSet같은 경우 저장된 Data의 정렬 순서대로 내부적 저장
그래서 만약 TreeSet에 문자열 저장하면 알파벳대로 저장.
그렇지만 내부적으로 TreeSet은 데이터 정렬에 손을 쓴만큼 조회 속도가 느려짐.
그래서 해당 부분은 의식해야함.
Generic
Generic은 클래스 내부에서 지정하는 것이 아닌 외부에서 사용자에 의해 지정되는 것이다.
특정(Specific) Type을 미리 지정하는 것이 아닌 필요에 의해 지정할 수 있는 Generic Type이라는 의미.
자세한 내용은 후에 블로그에 따로 작성하고 간단하게 생각해보자면 장점은 다음과 같다.
1. Generic을 사용하면 잘못된 Type이 Class에 들어오는 것을 Compile Level에서 방지할 수 있다.
2. Class 외부에서 Type을 지정하여, Type Check 및 Change의 필요성이 없어 관리가 편하다.
3. Code의 재사용성이 높아진다.
자주 봤던 형태로 ArrayList<>(); 에서 <>에 속한다.
- Generic Type
| Type | Descriptions |
|---|---|
<T> | Type |
<E> | Element |
<K> | Key |
<V> | Value |
<N> | Number |
해당 키워드는 암묵적인 규칙일 뿐, 변경하여도 상관없다고 한다.
DFS와 BFS
DFS와 BFS에 대한 구현은 후에 따로 작성하고 두 개의 특징만 간단히 작성하겠다.
1. DFS
DFS의 경우는 면적을 계산하는 문제나, 군집의 갯수를 파악하는 경우 또는 연결된 노드의 경로에 특징을 저장해야하는 문제에서 DFS를 사용한다.
2. BFS
BFS는 미로 찾기처럼 최단거리를 구해야 할 경우 더 유리하다.
너비 우선에서는 가장 먼저 찾는 경우가 최단거리이기 때문이다.
새싹