코딩테스트 필수 Java 문법 및 자료구조 정리
Java 문법 및 자료구조
Java 변수 타입
| 프리미티브 타입 | int, long, float, double, char 등 |
| 레퍼런스 타입 | Integer, Long, Float, Double, Character 등 |
참조형 변수인 레퍼런스 타입은 메모리에 직접 값을 저장하는 프리미티브 타입보다 연산 속도가 느리고,
컬렉션 프레임워크에 저장할 때 주로 사용됩니다.
숫자형
// 더하기
a + b
// 빼기
a - b
// 곱하기
a * b
// 나누기 (소수점 버림)
a / b
// 나눈 나머지 반환 (소수점 버림)
a % b
// a가 b보다 크면 양수, 작으면 음수, 같으면 0 반환
Integer.compare(a, b);
// 이진수를 정수로 변환
Integer.parseInt(이진수, 2);
// 정수를 이진수 문자열로 변환
Integer.toString(정수, 2);
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);
문자열
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("문자열", "");
// 정규표현식으로 해당하는 문자 모두 삭제
str = str.replaceAll("[aeiou]", "");
// 정규표현식으로 해당하는 문자가 1개 이상이면 공백 1개로 치환
str = str.replaceAll("[aeiou]+", " ");
// 정규표현식으로 모든 영어 소문자, 대문자, 한글, 숫자 삭제
str = str.replaceAll("[a-zA-Z가-힣0-9]", "");
// 정규표현식으로 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(숫자);
// 문자열을 int로 변환
if (!str.isEmpty()) {
int i = Integer.parseInt(str);
}
// 문자열을 Integer로 변환
if (!str.isEmpty()) {
Integer i = Integer.valueOf(str);
}
// 문자를 정수로 변환 ('1'은 아스키코드 49이므로, '0'을 빼야 정수 1)
char character = '1';
int i = character - '0';
// 문자열을 문자열 배열로 변환
String[] strArr = str.split("");
// 정규표현식으로 1개 이상 공백을 기준하여 자르기
String[] strArr = str.split("[ ]+");
// 배열, Set 등 객체를 문자열로 이어붙이기
String.join("구분자", 객체);
// 문자열을 전부 소문자로 변환
str.toLowerCase();
// 문자열을 전부 대문자로 변환
str.toUpperCase();
StringBuilder
// StringBuilder를 이용한 효율적 문자열 더하기
StringBuilder sb = new StringBuilder();
sb.append("문자열");
sb.append("문자열2");
// 특정 문자가 있는 인덱스 반환
sb.toString().indexOf("문자");
// 3번째 문자열 삭제
sb.deleteCharAt(3);
// 1번째 인덱스에 문자열 추가
sb.insert(1, "문자열");
// sb 문자열을 Long으로 변환
long l = Long.parseLong(sb.toString());
멀티스레드 환경에서는 Thread-Safe 한 StringBuffer를 사용해야 합니다.
배열 (Array)
생성한 배열 크기를 변경할 수 없으므로, 저장할 데이터의 개수를 알 수 있을 때 사용합니다.
보통 1차원 배열은 1,000만개, 2차원 배열은 3,000 * 3,000 크기를 넘으면 배열 할당이 실패될 수 있습니다.
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} }
// 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[] slicedArr = 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();
}
}
}
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)
가변 크기의 동적 배열이므로 데이터를 자유롭게 삽입/삭제할 수 있습니다.
데이터 접근은 시간복잡도가 O(1)으로 빠르고, 중간 데이터 삽입/삭제는 O(n)으로 느립니다.
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));
// 배열을 리스트로 변환
ArrayList<Integer> list = new ArrayList<>(Arrays.asList(배열));
// 리스트를 배열로 변환
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(0, 값);
// 리스트의 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(값)) {}
// 리스트 오름차순 정렬 : O(nlogn)
Collections.sort(list);
// 리스트 내림차순 정렬 : O(nlogn)
Collections.sort(list, Collections.reverseOrder());
// 리스트의 인덱스 1부터 5 앞까지의 요소를 정렬
Collections.sort(list.subList(1, 5));
}
}
연결리스트 (LinkedList)
원소가 데이터-포인터로 구성되어 있고, 포인터는 다음 원소 메모리 위치를 가리킵니다.
데이터가 메모리 상 흩어져 저장되어, 앞 원소부터 순회해야 원하는 데이터에 접근할 수 있습니다.
데이터 추가는 추가할 위치의 앞/뒤 원소 포인터를 변경하면 되어서 O(1)으로 간단합니다.
// 연결리스트 객체 생성
LinkedList<String> list = new LinkedList<>();
// 연결리스트 마지막에 원소 추가 : O(1)
list.add("값");
// 연결리스트 원소 삭제 : O(n)
list.remove("값");
// 연결리스트 원소 인덱스 반환 : O(n)
list.indexOf("값");
// 연결리스트 3번째 원소 원소 탐색 : O(n)
list.get(2);
// 연결리스트 전체 삭제
list.clear();
스택 (Stack)
먼저 입력한 데이터를 나중에 꺼내는 선입후출(FILO) 자료구조입니다.
최근에 삽입한 데이터를 대상으로 연산할 때 사용하면 좋습니다.
// Deque를 구현한 스택 객체 생성
Deque<Integer> stack = new ArrayDeque<>();
// 또는 Stack<Integer> stack = new 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());
}
큐 (Queue)
먼저 입력한 데이터를 먼저 꺼내는 선입선출(FIFO) 자료구조입니다.
작업 대기열이나 이벤트 처리에 사용하면 좋습니다.
Queue 인터페이스에 ArrayDeque 또는 LinkedList를 구현체로 사용하면 됩니다.
// Queue를 구현한 큐 객체 생성
Queue<Integer> queue = new ArrayDeque<>();
// 또는 Queue<Integer> queue = new LinkedList<>();
// 메모리 효율적이고 빠른 연산이 가능한 ArrayDeque 사용이 권장됩니다.
// 큐에 데이터 추가
queue.offer(1); // queue.add(1);은 큐에 공간이 부족하면 Exception을 발생합니다.
// 큐의 맨 앞 데이터를 제거하지 않고 반환
queue.peek();
// 큐의 맨 앞 데이터를 제거 후 반환
queue.poll();
// 큐가 비어있는지 확인
queue.isEmpty();
// 큐 전체 삭제
queue.clear();
덱 (ArrayDeque) ★
스택/큐와 달리, 양쪽에서 데이터를 삽입/삭제할 수 있는 자료구조입니다.
ArrayDeque를 응용하여 스택/큐를 구현하면 좋습니다.
힙 (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) -> { return b-a });
// 노드의 cost 값에 따라 오름차순 정렬하는 우선순위 큐 객체 생성
PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
// 컬렉션 객체의 모든 데이터를 담은 우선순위 큐 객체 생성
PriorityQueue<String> pq = new PriorityQueue<>(list);
// 컬렉션 객체의 모든 데이터를 우선순위 큐 객체에 삽입 : O(n)
pq.addAll(list);
// int 배열의 모든 데이터를 우선순위 큐 객체에 삽입 : O(n)
for (int v : intArr) {
pq.add(v);
}
// 값을 우선순위 큐에 삽입 : 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);
해시 (Hash)
해시 함수로 얻은 키의 해시 값을 size로 나눈 나머지 인덱스에 값을 저장하여 검색/삽입/삭제가 빠른 자료구조입니다.
키-값 데이터 쌍을 버킷이라 하고, 키로 검색하면 값을 O(1)으로 찾을 수 있습니다.
비밀번호, DB 인덱싱, 블록체인 등 검색 횟수가 많거나 보안이 필요한 경우 사용합니다.
HashMap
// 해시맵 객체 생성 (HashTable 클래스는 잘 사용되지 않습니다.)
HashMap<String, Integer> map = new HashMap<>();
// 해시맵 값 삽입 및 수정 : O(1) (같은 키 값으로 넣으면, 기존에 저장된 값이 수정됩니다.)
map.put("키", 값);
// 해시맵에서 키-값 삭제 : O(1)
map.remove("키");
// 해시맵에서 모든 데이터 삭제
map.clear();
// 해시맵에 데이터가 있는지 확인
map.isEmpty();
// 해시맵 데이터 개수 확인
map.size();
// 해시맵에 키가 있는지 확인 : O(1)
if (map.containsKey("키")) {
// 해시맵 값 출력
System.out.println(map.get("키"));
}
// 해시맵에 값이 있는지 확인 : O(1)
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);
}
해시테이블 충돌
해시테이블의 배열 크기가 작을수록 충돌 가능성과 선형 탐색의 빈도가 높아지게 됩니다.
반대로 배열 크기가 너무 크면 빈 버킷이 많아져서 메모리를 낭비하게 됩니다.
해시테이블 충돌 해결 방법
- 체이닝(연쇄법) : 각 버킷에 충돌된 데이터를 연결리스트 등으로 연결하여 저장하는 방법입니다.
집합 (Set)
중복이 없는 원소들을 갖는 자료구조입니다.
HashMap처럼 키-값이 아니라, 키만 있는 경우 사용하면 좋습니다.
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'));
for (int i : arr) {
// 값이 해시셋에 있는지 확인 : O(1)
if (set.contains(i)) {
return true;
}
// 해시셋에 현재 값 저장 : O(1)
set.add(i);
}
// 해시셋 데이터 개수 확인
set.size();
// 해시셋 데이터 삭제 : 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;
}
TreeSet : 이진 검색 트리 기반으로 구현되어 있으며, 중복을 제거하고 정렬 조건에 맞게 정렬됩니다.
// 중복값 제거, 오름차순 정렬 세팅 (기본값)
TreeSet<Integer> set = new TreeSet<>();
// 중복값 제거, 내림차순 정렬 세팅 : O(nlogn)
TreeSet<Integer> set = new TreeSet<>(Collections.reverseOrder());
for (int num : arr) {
set.add(num);
}
// int형 배열에 담기
int[] result = new int[set.size()];
int i = 0;
for (int v : set) {
result[i++] = v;
}
// 트리셋이 비어있는지 확인
set.isEmpty();
// 트리셋 데이터 삭제 : O(logn)
set.remove(값);
트리 (Tree)
계층 구조 데이터를 저장하고 표현하기 위한 자료구조입니다.
인공지능의 의사 결정 트리, 자동 완성 기능, 데이터베이스(B-트리, B+트리) 등에 사용합니다.
이진 트리는 모든 노드의 최대 차수(자식 노드 수)가 2인 트리입니다.
이진 탐색 트리
왼쪽 가지의 모든 자식이 부모보다 작고, 오른쪽 가지의 모든 자식이 부모보다 큰 트리입니다.
왼쪽 가지의 끝에 최소 노드가 있고, 오른쪽 가지의 끝에 최대 노드가 있습니다.
트리가 직선에 가까워지면 선형 탐색처럼 성능이 나빠서, 자가균형 이진탐색트리로 탐색 효율을 유지하면 좋습니다.
그래프 (Graph)
노드와 방향/무방향 간선을 이용한 비선형 자료구조입니다.
간선에는 가중치가 존재할 수 있습니다.
Java 코드 실행시간 계산 방법
long start = System.currentTimeMillis();
// 실행시간을 계산할 코드 작성
long end = System.currentTimeMillis();
System.out.println(((end - start) / 1000.0) + "초");
컴퓨터가 초당 연산할 수 있는 최대 횟수는 1억입니다.
Leave a comment