코딩테스트 필수 Java 문법 및 자료구조 정리
Java 자료구조
Java 데이터 타입 종류
| 프리미티브 타입 (기본 데이터 타입) |
메모리에 값을 직접 저장해서 연산 속도가 빠릅니다. 예시 : int, long, float, double, char 등 |
| 레퍼런스 타입 (참조 데이터 타입) |
메모리에 값이 들어있는 객체의 주소를 저장합니다. 컬렉션 프레임워크 클래스의 제네릭에는 프리미티브 타입이 아닌 레퍼런스 타입 객체를 사용해야 합니다. 예시 : 프리미티브 타입을 객체로 감싸는 래퍼 클래스 (Integer, Long, Float, Double, Character 등) / 컬렉션 프레임워크 클래스 (ArrayList, HashMap, TreeSet 등) / 일반 클래스 (String, Scanner, 사용자 정의 클래스 등) / 배열 (int[], String[] 등) / 인터페이스 / 상수 열거형 타입 (enum) |
숫자형
// 더하기
a + b
// 빼기
a - b
// 곱하기
a * b
// 나누기 (소수점 버림)
a / b
// 나눈 나머지 반환 (소수점 버림)
a % b
// a가 b보다 크면 양수, 작으면 음수, 같으면 0 반환
Integer.compare(a, b);
// 문자열을 정수로 변환
Integer.parseInt("문자열");
// 이진수를 정수로 변환
Integer.parseInt(이진수, 2);
// 정수를 이진수 문자열로 변환
Integer.toString(정수, 2);
// int 최대값 (최소값 구할 때 초기값으로 사용)
Integer.MAX_VALUE
// int 최소값 (최대값 구할 때 초기값으로 사용)
Integer.MIN_VALUE
Math 함수
// 올림
Math.ceil(숫자);
// 올림 한 실수 값을 정수로 반환
return (int) Math.ceil((double) 숫자1 / 숫자2);
// 반올림
Math.round(숫자);
// 소수점 둘째 자리에서 반올림
Math.round(1.234 * 100) / 100;
// 100을 곱해서 소수점 둘째 자리까지 정수로 만들고, 반올림 후 원래 자리수로 되돌림
// 내림
Math.floor(숫자);
// 거듭제곱
Math.pow(2, 8); // 2의 8승 = 256.0
// 제곱근
Math.sqrt(숫자);
// 제곱수 판별
if (Math.sqrt(숫자) % 1 == 0)
// 최대값 반환
Math.max(숫자1, 숫자2);
// 절대값 반환 (양수는 그대로, 음수는 양수로 부호 제거하여 반환)
Math.abs(숫자);
문자형
// 문자열을 char 배열로 변환하고 각 문자 반복
for (char c : str.toCharArray()) { }
// 문자열 i번째 문자 반환
char c = str.charAt(i);
// 대소문자 여부 확인
Character.isUpperCase(c);
// 대문자로 변환
Character.toUpperCase(c);
// 소문자로 변환
Character.toLowerCase(c);
// 문자가 숫자인지 판별
Character.isDigit('문자');
// 문자형 배열을 문자열로 변환
char[] chars = {'H', 'e', 'l', 'l', 'o'};
String str = String.valueOf(chars);
// 알파벳 더하기
char c = 'A' + 1; // 결과 : B (char 형에 int를 더하면 char로 자동 형변환)
문자열
Java에서 String은 값을 변경할 수 없는 객체입니다.
문자열 수정 시 기존 객체를 수정하지 않고 새로운 객체를 반환합니다.
String
// 비효율적 문자열 더하기 (값 복사 n * 값 저장 n) : O(n²)
String str = "문자열";
System.out.println(System.identityHashCode(str)); // 객체 해시코드 : 1808253012
str += "문자열2";
System.out.println(System.identityHashCode(str)); // 객체 해시코드 : 589431969 (다른 객체가 됨)
// 문자열 모두 삭제
str = str.replace("1", ""); // 문자열에서 "1" 전체 삭제
// 앞에서부터 처음 발견한 문자열 하나만 삭제
str = str.replaceFirst("문자열", "");
// replace 함수 : 정규표현식 사용 불가
// replaceAll 함수 : 정규표현식 사용 가능
// 정규표현식으로 해당하는 문자 모두 삭제
str = str.replaceAll("[aeiou]", "");
// 정규표현식으로 해당하는 문자가 1개 이상이면 공백 1개로 치환
str = str.replaceAll("[aeiou]+", " ");
// 정규표현식으로 모든 영어 소문자, 대문자, 한글, 숫자 삭제
str = str.replaceAll("[a-zA-Z가-힣0-9]", "");
// 정규표현식으로 영어 외 모두 제거
str = str.replaceAll("[^a-zA-Z]", "");
// 정규표현식으로 l~z에 해당하지 않는 문자 모두 변경
str = str.replaceAll("[^l-z]", "l");
// 문자열을 n번 반복한 문자열 생성
str = str.repeat(n);
// 0번째부터 5번째 앞까지 문자열 추출
str.substring(0, 5);
// 앞에서부터 탐색하여, 문자가 저장된 인덱스 반환 (없으면 -1 반환)
str.indexOf(문자);
// 뒤에서부터 탐색하여, 문자가 저장된 인덱스 반환 (없으면 -1 반환)
str.lastIndexOf(문자);
// 문자로 시작하는 문자열이면 true 반환
str.startsWith(문자);
// 문자로 끝나는 문자열이면 true 반환
str.endsWith(문자);
// 문자열이 포함되어 있는지 확인
str.contains(문자열);
// 정수, 문자 등 다른 타입을 문자열로 변환
String str = String.valueOf(숫자);
String str = String.valueOf(문자);
// 문자열을 int로 변환
if (!str.isEmpty()) {
// String만 변환 가능 (문자형 배열은 변환 불가)
int i = Integer.parseInt(str);
}
// 문자열을 Integer로 변환
if (!str.isEmpty()) {
Integer i = Integer.valueOf(str);
}
// 문자를 정수로 변환 ('1'은 아스키코드 49이므로, 아스키코드 48인 '0'을 빼야 정수 1로 변환)
char c = '1';
int i = c - '0';
// 문자열을 문자열 배열로 변환
String[] letters = str.split("");
// 정규표현식으로 1개 이상 공백을 기준하여 자르기
String[] words = str.split("[ ]+");
// 배열, Set 등 객체를 문자열로 이어붙이기
String.join("구분자", 객체);
// 문자열을 전부 소문자로 변환
str.toLowerCase();
// 문자열을 전부 대문자로 변환
str.toUpperCase();
StringBuilder
// StringBuilder를 이용한 효율적 문자열 더하기
StringBuilder sb = new StringBuilder("초기문자열");
sb.append("문자열1");
sb.append("문자열2");
// StringBuilder를 이용한 문자열 오름차순 정렬
char[] chars = str.toCharArray();
Arrays.sort(chars);
StringBuilder sb = new StringBuilder();
for (char c : chars) {
sb.append(c);
}
System.out.println(sb.toString());
// 특정 문자가 있는 인덱스 반환
sb.toString().indexOf("문자");
// 3번째 문자열 삭제
sb.deleteCharAt(3);
// StringBuilder 값 삭제
sb.setLength(0);
또는
sb.delete(0, sb.length());
// 1번째 인덱스에 문자열 추가
sb.insert(1, "문자열");
// 문자열 역순으로 정렬
sb = sb.reverse();
// sb 문자열을 Long으로 변환
long l = Long.parseLong(sb.toString());
멀티스레드 환경에서는 Thread-Safe 한 StringBuffer를 사용해야 합니다.
배열 (Array)
선언 시 할당한 고정적인 메모리에 데이터를 순차적으로 저장하는 자료구조입니다.
배열은 크기 변경이 불가하므로, 저장할 데이터 수가 고정된 경우 사용합니다.
장점 : 데이터 조회, 마지막 원소 삽입/삭제는 O(1)으로 빠릅니다.
중간 원소 삽입/삭제는 뒤 원소들을 한 칸씩 shift 해서 O(n)이 됩니다.
단점 : 선언 시 할당한 메모리 크기보다 더 많은 데이터를 저장할 수 없고, 적은 데이터를 저장하면 메모리가 낭비될 수 있습니다.
Array에 미리 예상한 것보다 많은 데이터를 저장하려면?
메모리 크기가 고정된 Array와 달리,
할당된 메모리를 초과하면 자동으로 리사이징하여 데이터를 저장하는
Dynamic Array를 구현한 ArrayList를 사용하면 됩니다.
동적 배열 리사이징 전략
Doubling : 기존 배열 사이즈의 두 배를 선언하고 데이터를 옮기는 방식으로 확장합니다.
ArrayList는 더블링 대신 1.5배씩 용량을 증가시키는 방식을 사용합니다.
분할상환 시간복잡도
Dynamic Array의 append 시간복잡도는 가끔 모든 데이터를 옮길 때 O(n)이지만,
자주 발생하는 평소 append는 O(1)이므로 분할하여 나눠가지면 최종적으로 O(1)이 됩니다.
1차원 배열 사용법
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
// 배열 생성
int[] arr = { 1, 2, 3, 4, 5 };
int[] arr = new int[] { 1, 3, 5, 7, 9 };
int[] arr = new int[5]; // { 0, 0, 0, 0, 0 }
// 2차원 배열 생성
int[][] arrs = new int[][] { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int[][] arrs = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
int[][] arrs = new int[3][]; // { null, null, null }
int[][] arrs = new int[3][3]; // { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} }
// 1차원 배열 모든 원소 값 변경
Arrays.fill(arr, 값);
// 2차원 배열 모든 원소 값 변경
for (int i = 0; i < arrs.length; i++) {
Arrays.fill(arrs[i], 값);
}
// 0번째 원소 값을 1으로 변경 : O(1)
arr[0] = 1;
// 3번째 값 접근 : O(1)
System.out.println(arr[2]);
// 배열 전체 출력 : O(n)
System.out.println(Arrays.toString(arr));
// [1, 2, 3, 4, 5]
// 배열 데이터 개수
arr.length;
// 배열 오름차순 정렬 : O(nlogn)
Arrays.sort(arr);
// 기본형 int 배열은 내림차순 정렬이 불가해서, Integer[]로 변환
Integer[] int_array = new Integer[arr.length];
for (int i = 0; i < arr.length; i++) {
int_array[i] = arr[i];
}
// 내림차순 정렬
Arrays.sort(int_array, Collections.reverseOrder());
// 배열의 인덱스 1부터 4까지의 요소를 정렬
Arrays.sort(arr, 1, 5);
// 람다식은 한 번만 실행할 목적으로 코드를 간결하게 표현하는 익명 함수입니다.
// 배열에 저장된 객체의 int 변수 값을 람다 함수로 받아서 비교 후 오름차순 정렬합니다.
Arrays.sort(배열, (객체명 o1, 객체명 o2) -> Integer.compare(o1.int변수명, o2.int변수명));
// o1 > o2면 1을 반환하여 서로의 위치를 변경합니다.
// 배열 깊은 복사 ★
int[] clone = arr.clone();
// 배열 자르기 (i번째부터 j번째까지)
int[] slice = Arrays.copyOfRange(arr, i-1, j);
// Integer 배열을 int 배열로 변환
int[] arr = new int[integer배열.length];
for (int i = 0; i < integer배열.length; i++) {
arr[i] = integer배열[i].intValue();
}
// 배열 비교
if (Arrays.equals(arr1, arr2)) {
}
}
}
2차원 배열 사용법
import java.util.Arrays;
public class Solution {
public static void main(String[] args) {
// 2차원 배열 생성
int[][] arr = { {1,2,3}, {4,5,6} }; // 2행 3열
// 1번째 배열의 2번째 값 변경
arr[1][2] = 7;
// 2차원 배열 값 출력
System.out.println(arr[1][2]);
2차원 배열 전체 출력
System.out.println(Arrays.deepToString(arr));
}
}
배열은 차원과는 무관하게, 메모리에 연속 할당됩니다.
ArrayList
가변 크기의 동적 배열 기반으로 구현된 리스트 자료구조입니다.
인덱스 위치의 데이터에 빠르게 접근할 수 있습니다.
ArrayList 사용법
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
// import java.util.*; 으로 한번에 가능
public class Solution {
public static void main(String[] args) {
// 리스트 객체 생성
ArrayList<Integer> list = new ArrayList<>();
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
// 배열을 리스트로 변환 (크기 고정 리스트)
List<String> fixedSizeList = Arrays.asList(String배열명);
// 배열을 ArrayList로 변환 (크기 변경 가능 리스트)
ArrayList<String> list = new ArrayList<>(Arrays.asList(String배열명));
// 리스트를 배열로 변환
int[] arr = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
arr[i] = list.get(i);
}
// 해시맵의 값으로 리스트 객체 생성
ArrayList<Integer> list = new ArrayList<>(map.values());
// 리스트 마지막에 원소 추가 : O(1)
list.add(값);
// 인덱스 위치에 원소 삽입 : O(n)
// 뒤 원소들이 한 칸씩 이동되어서 시간복잡도가 높아집니다.
list.add(2, 값);
// 인덱스 위치 값 수정
list.set(2, 값);
// 리스트의 0번째 원소 출력 : O(1)
// 조회 시 인덱스로 바로 접근해서 빠릅니다.
System.out.println(list.get(0));
// 리스트 마지막 원소 삭제 : O(1)
list.remove(list.size() -1);
// 리스트 첫번째 원소 삭제 : O(n)
list.remove(0);
// 리스트에서 값에 해당하는 첫번째 원소 삭제 : O(n)
list.remove("값");
또는
list.remove((Integer) 값);
// 리스트 전체 출력
System.out.println(list);
// 리스트 복사
ArrayList<Integer> list2 = new ArrayList<>(list);
// 리스트 데이터 개수
list.size();
// 리스트가 비어있는지 확인
if (list.isEmpty()) { }
// 리스트에 값이 있는지 확인
if (list.contains(값)) {}
// 리스트에서 해당 값이 있는 첫 번째 인덱스 반환
list.indexOf(값);
// 리스트 오름차순 정렬 : O(nlogn)
Collections.sort(list);
// 리스트 내림차순 정렬 : O(nlogn)
Collections.sort(list, Collections.reverseOrder());
// 리스트의 인덱스 1부터 5 앞까지의 요소를 정렬
Collections.sort(list.subList(1, 5));
}
}
LinkedList
이중 연결 리스트 기반으로 구현된 리스트 자료구조입니다.
메모리에 불연속적으로 저장되지만, 각 노드에 값과 다음 노드 주소 포인터를 저장하여 논리적 연속성을 가집니다.
선언 시 메모리를 할당하는 Array와 달리, 데이터가 추가되는 시점에 메모리를 할당하여 효율적입니다.
장점 : 저장할 데이터 개수를 미리 알 수 없을 때 사용하면 좋습니다.
단점 : 다음 노드 주소를 저장하여 메모리를 더 차지하고, 검색 시 앞 원소부터 순회하므로 O(n)으로 느립니다.
원소 추가/삭제는 앞/뒤 원소 포인터를 변경하면 되어서 O(1)이지만, 해당 위치까지 순회하여 도달하므로 O(n) 입니다.
LinkedList 사용법
// 연결리스트 객체 생성
LinkedList<String> list = new LinkedList<>();
// 연결리스트 마지막에 원소 추가 : O(1)
// 마지막 노드를 가리키는 포인터가 있어서 빠르게 추가할 수 있습니다.
list.add("값");
// 연결리스트 중간 원소 추가 : O(n)
list.add(인덱스, "값");
// 연결리스트 중간 원소 삭제 : O(n)
list.remove("값");
// 연결리스트 원소 인덱스 반환 : O(n)
list.indexOf("값");
// 연결리스트 3번째 원소 원소 탐색 : O(n)
// 앞 원소부터 순차적으로 타고 들어가서 느립니다.
list.get(2);
// 연결리스트 전체 삭제
list.clear();
연결리스트는 노드 데이터 외에도 이전/다음 노드 포인터를 저장하므로 배열보다 추가 메모리가 필요합니다.
스택 (Stack)
나중에 들어온 데이터가 먼저 나가는 후입선출(LIFO) 자료구조입니다.
Call Stack, 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록, DFS 시 활용하면 좋습니다.
// Deque를 구현한 스택 객체 생성
Deque<Integer> stack = new ArrayDeque<>();
// 또는 Stack<Integer> stack = new Stack<>();
// Stack보다 메모리 효율적이고 성능이 좋은 ArrayDeque 사용이 권장됩니다.
// 스택에 데이터 삽입 : O(1)
stack.push(1);
// 스택에서 마지막 데이터를 제거하지 않고 반환
stack.peek();
// 스택이 비어있지 않은지 확인 (스택이 비어있을 때 pop 하면 EmptyStackException 발생)
if (!stack.isEmpty()) {
// 스택에서 마지막 데이터 제거 후 반환 : O(1)
stack.pop();
};
// 스택 데이터 개수
stack.size();
// 스택 전체 삭제
stack.clear();
// 스택의 모든 요소를 문자열로 더하기 : O(n)
StringBuilder sb = new StringBuilder();
while (!stack.isEmpty()) {
sb.append(stack.pop());
}
// 스택의 모든 요소 순회
for (Integer x : stack) {
// 스택 pop 순서와 달리, push 했던 순서대로 앞에서부터 순회합니다.
}
큐 (Queue)
먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO) 자료구조입니다.
캐시 구현, 작업 대기열, 프로세스 관리, 이벤트 처리, BFS 시 활용하면 좋습니다.
Queue 인터페이스에 ArrayDeque 또는 LinkedList를 구현체로 사용하면 됩니다.
// Queue를 구현한 큐 객체 생성
Queue<Integer> queue = new ArrayDeque<>();
// 또는 Queue<Integer> queue = new LinkedList<>();
// Queue보다 메모리 효율적이고 빠른 연산이 가능한 ArrayDeque 사용이 권장됩니다.
// 큐에 데이터 추가 (enqueue) : O(1)
queue.offer(1); // queue.add(1);은 큐에 공간이 부족하면 Exception을 발생합니다.
queue.offer(null); // NullPointerException 발생
// 큐의 맨 앞 데이터를 제거하지 않고 반환
queue.peek();
// 큐의 맨 앞 데이터를 제거 후 반환 (dequeue) : O(1)
queue.poll();
// 큐에 값이 포함되어 있는지 확인 : O(n)
queue.contains(값);
// 큐가 비어있는지 확인
queue.isEmpty();
// 큐 전체 삭제
queue.clear();
// 큐 순회 : O(n)
for (객체명 객체변수명 : queue) {
}
덱 (ArrayDeque) ★
스택/큐와 달리, 양쪽에서 데이터를 삽입/삭제할 수 있는 자료구조입니다.
ArrayDeque를 응용하여 스택/큐를 구현하는 것이 권장됩니다.
멀티스레드 환경이면 ConcurrentLinkedDeque 처럼 스레드 안전한 구현체 사용이 필요합니다.
힙 (Heap)
완전 이진 트리 자료구조이고, 빠르게 최소값 또는 최대값을 추출할 수 있습니다.
최대힙은 부모가 자식보다 크거나 같고, 최소힙은 부모가 자식보다 작거나 같아야 합니다.
힙에서는 루트만 꺼낼 수 있고, 중간 노드를 꺼낼 수 없습니다.
최소힙 원소 추가 예시
- 추가한 수를 힙의 가장 후미에 저장합니다.
- 부모의 수가 자식의 수보다 크면 수를 교환합니다.
- 부모의 수가 자식의 수보다 크지 않을 때까지 부모와 비교 및 교환을 반복합니다.
최소힙 원소 삭제 예시
- 가장 위에 있는 root 노드를 삭제합니다.
- 가장 후미에 있는 수를 root 노드로 이동합니다.
- root의 수가 자식들의 수보다 작은 경우, 더 작은 자식과 위치를 교환합니다.
- 부모의 수가 자식의 수보다 크지 않을 때까지 자식과 비교 및 교환을 반복합니다.
우선순위 큐 (PriorityQueue)
힙으로 구현된 완전 이진 트리 자료구조이며, 우선순위가 높은 순서로 원소를 poll 합니다.
작업 스케줄링, 응급실 대기열, 네트워크 트래픽 제어, 교통 네트워크 최적화 등에 활용됩니다.
// 오름차순 정렬하는 우선순위 큐 객체 생성 (기본적으로 Min Heap이라서 작은 값부터 나옵니다.)
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 내림차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<String> pq = new PriorityQueue<>(Collections.reverseOrder());
또는
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
또는
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> { b - a });
// b - a 방식은 결과값이 Integer 범위를 초과할 때 오버플로우가 발생하므로 지양하는 것이 좋습니다.
// 값 추가 시, int 배열 인덱스에 해당하는 값을 기준으로 오름차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(배열명[a], 배열먕[b]));
또는
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> { 배열명[a] - 배열먕[b] });
// 값 추가 시, int 배열 인덱스에 해당하는 값을 기준으로 내림차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(배열명[b], 배열먕[a]));
// 노드 추가 시, 노드의 cost 값에 따라 오름차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
// 노드 추가 시, 노드의 cost 값에 따라 내림차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o2.cost, o1.cost));
// 컬렉션 객체의 모든 데이터를 오름차순 정렬하여 담은 우선순위 큐 객체 생성
PriorityQueue<String> pq = new PriorityQueue<>(list);
// 컬렉션 객체의 모든 데이터를 우선순위 큐 객체에 삽입 : O(n)
pq.addAll(list);
// int 배열의 모든 데이터를 우선순위 큐 객체에 삽입 : O(nlogn)
for (int v : intArr) {
pq.add(v);
}
// 값을 우선순위 큐에 삽입 (트리 맨 뒤에 삽입 후 힙 높이만큼 부모와 비교하며 swap) : O(logn)
pq.add(값);
// 우선순위가 높은 루트 원소 제거 후 반환
// 마지막 원소를 루트로 옮기고, 트리 높이만큼 비교 및 교환 (우선순위에 따라 힙 재정렬) : O(logn)
pq.poll();
// 우선순위 큐 객체의 모든 데이터를 배열에 삽입 : O(nlogn)
int i = 0;
while(!pq.isEmpty()) {
answer[i++] = pq.poll();
}
// 우선순위 큐 전체 출력 (우선순위 큐는 꺼내면서 정렬하므로, 삽입 후 pq는 정렬된 상태가 아닙니다.)
System.out.println(pq);
큐 자료구조로 우선순위 큐 구현 방법
class 객체명 {
int id;
int priority;
public 객체명(int id, int priority) {
this.id = id;
this.priority = priority;
}
}
class Main {
public int solution(int n, int m, int[] arr) {
Queue<객체명> queue = new ArrayDeque<>();
int answer = 0;
for (int i = 0; i < n; i++) {
// 객체 추가 (기존 순번, 우선순위 값)
queue.offer(new 객체명(i, arr[i]));
}
// 큐 순회
while (!queue.isEmpty()) {
객체명 current객체명 = queue.poll();
// 더 높은 우선순위가 있는지 여부
boolean hasHigher = false;
// 큐에서 꺼낸 현재 객체보다
// 우선순위가 높은 객체가 있으면 다시 넣기
for (객체명 객체변수명 : queue) {
if (객체변수명.priority > current객체명.priority) {
queue.offer(current객체명);
hasHigher = true;
break;
}
}
// 현재 꺼낸 객체 우선순위가 가장 높은 경우
if (!hasHigher) {
answer++;
// arr m번째 객체가 우선순위에 의해 꺼내진 순서 반환
if (current객체명.id == m) {
return answer;
}
}
}
return -1;
}
}
PriorityQueue 객체를 이용하면 더 편하게 우선순위 큐를 구현할 수 있지만,
기존 Qeuue 객체로도 우선순위 큐를 구현할 수 있습니다.
키-값 자료구조 (Map)
HashMap
키-값 쌍으로 데이터를 저장하고, 순서를 보장하지 않는 자료구조입니다.
같은 키로 값을 넣으면 기존 값에 덮어써져 중복이 제거됩니다.
해시 함수에 키를 입력하여 얻은 해시값을 버킷 배열 크기로 나눈 인덱스 주소에 값을 저장하여
검색/삽입/삭제 평균 시간복잡도가 O(1)으로 빠릅니다.
검색이 많은 서비스, 캐싱, 데이터베이스 인덱싱 등에 주로 사용됩니다.
// 해시맵 객체 생성 (HashTable 클래스는 잘 사용되지 않습니다.)
HashMap<String, Integer> map = new HashMap<>();
HashMap<String, HashSet<String>> setMap = new HashMap<>();
// 해시맵 값 삽입 및 수정 : O(1)
// 해시 충돌이 많은 최악의 경우 O(n)
map.put("키", 값);
// 해시맵에 키가 없으면 키 생성 후 초기값 저장
setMap.putIfAbsent("키", new HashSet<>());
// 이후 setMap.get("키").add("값"); 형태로 HashSet에 값 추가 가능
// 다른 맵 키-값 전체 복사
map.putAll(다른맵객체);
또는
new HashMap<>(configProperties);
// 해시맵에서 키-값 삭제 : O(1)
map.remove("키");
// 해시맵에서 모든 데이터 삭제
map.clear();
// 해시맵에 데이터가 있는지 확인
map.isEmpty();
// 해시맵 데이터 개수 확인
map.size();
// 해시맵에 키가 있는지 확인 : O(1)
if (map.containsKey("키")) {
// 해시맵 값 출력
System.out.println(map.get("키"));
}
// 해시맵에 값이 있는지 확인 : O(n)
if (map.containsValue(값)) {
System.out.println("값이 존재합니다."));
}
// 값이 없으면 기본값 출력
map.getOrDefault("키", 기본값);
// 해시맵 전체 출력
System.out.println(map);
// 해시맵 키셋 순회하며 값 출력
Set<String> keySet = map.keySet();
for (String key : keySet) {
System.out.println(map.get(key));
}
// 해시맵 값 순회하며 출력
for (Integer val : map.values()) {
System.out.println(val);
}
// 해시맵 비교 (키, 값이 모두 같으면 true 반환)
map1.equals(map2);
해시테이블 충돌 이유
서로 다른 키가 같은 버킷 인덱스로 매핑될 때 충돌이 발생합니다.
해시테이블의 버킷 배열 크기가 작을수록 충돌 가능성과 선형 탐색의 빈도가 높아지게 됩니다.
반면, 배열 크기가 너무 크면 빈 버킷이 많아져서 메모리를 낭비하게 됩니다.
해시테이블 충돌 해결 방법
- 체이닝 (연쇄법) : 충돌된 엔트리 (키-값 쌍) 들을 연결리스트/트리 등으로 연결하여 같은 버킷에 저장하는 방식입니다.
- Open Addressing : 충돌 발생 시, 다른 빈 버킷을 찾아 데이터를 저장하는 방식입니다.
TreeMap
키-값 쌍으로 데이터를 저장하고, 정렬 조건에 따라 키가 정렬되는 자료구조입니다.
같은 키로 값을 넣으면 기존 값에 덮어써져 중복이 제거됩니다.
// 중복값 제거, 오름차순 정렬 세팅 (기본값)
TreeMap<String, String> treeMap = new TreeMap<>();
// 중복값 제거, 내림차순 정렬 세팅
TreeMap<String, String> treeMap = new TreeMap<>(Collections.reverseOrder());
// TreeMap에 데이터 추가 : O(logn)
treeMap.put("키", "값");
// 키-값 제거 : O(logn)
treeMap.remove("키");
// 키에 해당하는 값 반환 : O(logn)
treeMap.get("키");
// 특정 키가 있는지 확인
if (treeMap.containsKey(키)) {
}
// treeMap이 비어있는지 확인
if (treeMap.isEmpty()) {
}
// TreeMap 키 순회 (정렬된 순서대로 나옴)
for (String key : treeMap.keySet()) {
}
// TreeMap 값 순회 (정렬된 순서대로 나옴)
for (String value : treeMap.values()) {
}
// 값이 없으면 기본값 출력
treeMap.getOrDefault("키", 기본값);
집합 (Set)
중복 없이 원소들을 저장하는 자료구조입니다.
Map처럼 키-값이 아니라, 값만 저장하는 경우 사용하면 좋습니다.
HashSet
해시테이블 기반으로 구현 되어있으며, 순서를 보장하지 않는 집합입니다.
// 중복을 허용하지 않는 Hash 집합(Set) 생성
Set<Integer> set = new HashSet<>();
// 배열을 List로 변환 후 HashSet 기본 값으로 생성
Set<String> set = new HashSet<>(Arrays.asList(String배열));
// List 원소 생성 후 HashSet 기본 값으로 생성
Set<Character> set = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));
// set1 복제 후, set2에 없는 원소 제거 = 교집합 생성
Set<Integer> interSet = new HashSet<>(set1);
interSet.retainAll(set2);
// set1에서 set2 전체 원소 제거 = 차집합 생성
set1.removeAll(set2);
// 배열 순회
for (int i : arr) {
// HashSet에 값이 있는지 확인 : O(1)
// List contains는 O(n)이므로, HashSet으로 변환하여 값을 찾으면 훨씬 효율적입니다.
if (set.contains(i)) {
return true;
}
// HashSet에 현재 값 저장 : O(1)
set.add(i);
}
// HashSet 데이터 개수 확인
set.size();
// HashSet 데이터 삭제 : O(1)
set.remove(값);
배열에서 두 수의 합이 특정한 값이 되는지 O(1)으로 확인할 수 있습니다.
LinkedHashSet
중복을 제거하고 데이터를 추가한 순서대로 정렬합니다.
// LinkedHashSet 생성
Set<Character> set = new LinkedHashSet<>();
// 배열을 List로 변환 후 LinkedHashSet 기본 값으로 생성
Set<String> set = new LinkedHashSet<>(Arrays.asList(배열));
// 문자열의 문자를 set에 추가
for (char c : str.toCharArray()) {
set.add(c);
}
// 순서를 유지하고, 중복이 제거된 문자열 생성
String answer = "";
for (char c : set) {
answer += c;
}
// LinkedHashSet은 특정 인덱스에 해당하는 원소에 접근할 수 없습니다.
// Set 인터페이스는 인덱스 기반 접근을 지원하지 않습니다.
List<Integer> list = new ArrayList<>(set);
list.get(i);
// 위와 같이, 리스트로 변환하면 인덱스로 접근이 가능합니다.
TreeSet
Red-Black Tree 기반으로 구현되어 있으며, 정렬 조건에 따라 원소가 정렬되는 집합입니다.
// 중복값 제거, 오름차순 정렬 세팅 (기본값)
TreeSet<Integer> set = new TreeSet<>();
// 중복값 제거, 내림차순 정렬 세팅 : O(nlogn)
TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
for (int num : arr) {
// 원소 추가 후 트리 균형 유지 : O(logn)
set.add(num);
}
// int형 배열에 담기
int[] result = new int[set.size()];
int i = 0;
for (int v : set) {
result[i++] = v;
}
// TreeSet이 비어있는지 확인
set.isEmpty();
// TreeSet에 값이 있는지 확인 : O(logn)
if (set.contains(i)) {
// TreeSet은 자가균형 이진탐색트리로 이루어져 있으므로,
// 검색 시 트리 높이 (logn) 만큼 비교 연산을 수행하게 됩니다.
}
// TreeSet은 특정 인덱스에 해당하는 원소에 접근할 수 없습니다.
// TreeSet 데이터 삭제 : O(logn)
set.remove(값);
// 오름차순 TreeSet의 경우, 최소값/최대값 조회
int min = set.first();
int max = set.last();
트리 (Tree)
계층 구조 데이터를 저장하고 표현하기 위한 자료구조입니다.
인공지능의 의사 결정 트리, 자동 완성 기능, 데이터베이스 인덱스(B+Tree) 등에 사용합니다.
기본 트리 구현
// 원소 클래스 정의
class Node {
int vertex;
Node lt;
Node rt;
public Node(int vertex) {
this.vertex = vertex;
lt = null;
rt = null;
}
}
// 루트 노드 생성 후 하위 노드들 추가
Node root = new Node(0);
root.lt = new Node(1);
root.rt = new Node(2);
root.lt.lt = new Node(3);
root.lt.rt = new Node(4);
root.rt.lt = new Node(5);
root.rt.rt = new Node(6);
이진 트리 (Binary Tree)
모든 노드의 최대 자식 노드 수 (차수) 가 2인 트리 자료구조입니다.
완전 이진 트리
마지막 레벨을 제외한 모든 레벨 노드가 채워져있는 이진 트리입니다.
마지막 레벨 노드들은 왼쪽부터 차례대로 채워지게 됩니다.
이진 탐색 트리 (Binary Search Tree)
각 노드 값보다 작은 노드들은 왼쪽 서브트리, 큰 노드들은 오른쪽 서브트리에 저장하여 정렬된 이진 트리입니다.
왼쪽 가지의 끝에 최소 노드가 있고, 오른쪽 가지의 끝에 최대 노드가 있습니다.
BST의 검색/저장/삭제 시간복잡도는 O(logn) 이지만,
트리가 한쪽으로 치우쳐 직선에 가까워지면 선형 탐색처럼 탐색 성능이 O(n)이 될 수 있습니다.
트리가 평향되지 않게 삽입/삭제를 개선한 자가균형 이진 탐색 트리를 사용하면 좋습니다.
그래프 (Graph)
노드와 방향/무방향 간선으로 이루어진 비선형 자료구조입니다.
그래프 간선에는 가중치가 있을 수도 있습니다.
인접 행렬 그래프 구현
// 인접 행렬 그래프 생성
int[][] graph = new int[][];
// 간선 연결 정보 입력
for (int i = 0; i < 간선수; i++) {
int curVertex = sc.nextInt();
int nextVertex = sc.nextInt();
int cost = sc.nextInt();
// 행 노드에서 열 노드로 갈 수 있음 체크
graph[curVertex][nextVertex] = cost; // 가중치 그래프가 아니면 1 저장
// 무방향 그래프 (양방향 그래프) 인 경우 추가
graph[nextVertex][curVertex] = cost;
}
그래프를 인접 행렬 (2차원 배열) 형태로 저장하면 노드가 많고 간선이 적을수록 메모리가 낭비됩니다.
간선이 적으면 인접 리스트 형태로 현재 노드에서 갈 수 있는 노드만 저장하는 것이 좋습니다.
인접 리스트 그래프 구현
// 노드 클래스 정의
class Node {
int vertex;
int cost;
public Node(int vertex, int cost) {
this.vertex = vertex;
this.cost = cost;
}
}
// 인접 리스트 그래프 생성
List<List<Node>> graph = new ArrayList<>();
// 노드 리스트 추가
for (int i = 0; i < 노드수; i++) {
graph.add(new ArrayList<>());
}
// 간선 연결 정보 입력
for (int i = 0; i < 간선수; i++) {
int curVertex = sc.nextInt();
int nextVertex = sc.nextInt();
int cost = sc.nextInt();
// 현재 노드에서 갈 수 있는 다음 노드 추가
graph.get(curVertex).add(new Node(nextVertex, cost));
// 무방향 그래프 (양방향 그래프) 인 경우 추가
graph.get(nextVertex).add(new Node(curVertex, cost));
}
Java 객체 정렬 기준 커스텀 방법
정렬 기준 커스텀 클래스 정의
public class 클래스명 implements Comparable<클래스명> {
int x;
int y;
public 클래스명(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public int compareTo(클래스명 order) {
if (this.x != order.x) {
// x 값이 같지 않으면, x 기준 오름차순 (주 정렬 조건)
return Integer.compare(this.x, order.x);
} else {
// x 값이 같으면, y 기준 내림차순 (부 정렬 조건)
return Integer.compare(order.y, this.y);
}
}
}
클래스 정의 시 Comparable 인터페이스를 구현하고, compareTo 함수를 재정의하여 정렬 조건을 설정합니다.
Integer.compare 사용 시, 계산 결과가 int 범위를 초과하는 overflow 에러를 방지할 수 있습니다.
오름차순 시에는 Integer.compare(this.x, order.y); 처럼 음수를 리턴하면 됩니다.
정렬 기준 커스텀하기 좋은 클래스 종류
- 좌표를 저장하는 Point 클래스 : 좌표들을 특정 기준으로 정렬할 때 사용
- 간선 가중치를 저장하는 Edge 클래스 : 크루스칼 알고리즘에서 최소 스패닝 트리를 만들 때 사용
- 출발점에서 현재까지의 최소 거리를 저장하는 Node 클래스 : 다익스트라 알고리즘 등에서 사용
정렬 기준 커스텀 클래스 정렬 방법
ArrayList 정렬
// ArrayList 생성 및 원소 추가
ArrayList<클래스명> 클래스list = new ArrayList<>();
클래스list.add(new 클래스명(1, 5));
클래스list.add(new 클래스명(2, 3));
// list 내부 클래스의 compareTo 함수 기준 정렬
Collections.sort(클래스list);
객체 배열 정렬
// 객체 배열 생성 및 원소 추가
클래스명[] 클래스Arr = new 클래스명[개수];
클래스Arr[0] = new 클래스명(1, 5);
클래스Arr[1] = new 클래스명(2, 3);
// 배열 내부 클래스의 compareTo 함수 기준 정렬
Arrays.sort(클래스Arr);
우선순위 큐 정렬
// 우선순위 큐 생성 및 원소 추가
PriorityQueue<클래스명> pq = new PriorityQueue<>();
pq.offer(new 클래스명(1, 5));
pq.offer(new 클래스명(2, 3));
// 우선순위 큐 내부 클래스의 compareTo 함수 기준으로 정렬된 이진 힙에서 가장 최상위 객체 반환 후 재정렬
pq.poll();
Java 코드 실행시간 계산 방법
long start = System.currentTimeMillis();
// 실행시간을 계산할 코드 작성
long end = System.currentTimeMillis();
System.out.println(((end - start) / 1000.0) + "초");
컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억입니다.
Java 읽기 기본 코드
Scanner
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String word = sc.next();
Integer num = sc.nextInt();
String line = sc.nextLine();
}
}
Scanner는 간단한 데이터 입력을 받을 때 사용하면 좋습니다.
BufferedReader
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println(br.readLine());
}
}
BufferedReader는 Scanner보다 많은 입력을 빠르게 읽을 수 있어 알고리즘 문제에서 자주 사용됩니다.