코딩테스트 언어로 자바를 보는 곳이 많아 최근에 자바를 주력으로 공부하기 시작했다. 자바의 경우 메서드가 너무 많아 외우기 어려움이 있었는데 헷갈리는 부분을 한 곳에 정리해두려고 한다.
주의 사항
1. 내장 라이브러리
import java.lang.*; // 이건 자동으로 되서 생략 가능
import java.util.*;
import java.io.*;util과 io는 꼭 import 해주자.
참고: util.*은 Util의 모든 하위 패키지가 아닌 자식 패키지만 포함한다.
2. static
- Inner class 는 무조건 static으로 선언해야한다. 아니면 메모리 누수로 터진다.
- public satic void main 메서드에 의해 호출되는 코테의 경우 (ex 백준 엘리스) 별도 클래스를 만드는게 아니므로 반드시 static을 붙여서 변수나 메서드를 선언해야한다.
3. 엘리스 플랫폼 GC (Garbage Collector)
이건 좀 특이한 경우로 엘리스 플랫폼 코테에서 문제를 겪었다. 엘리스 코테에서는 kill proccess로 비정상적인 종료가 일어났는데, 이는 메모리 초과로 인한 현상이였다.
그러나 GC가 제대로 수거를 했다면 제대로 작동했을 코드여서 직접 메모리 사용을 코드로 조회해보았다. GC가 정리를 하는 시점이 주기적인 검사나 메모리가 꽉 찾을때 하는 것으로 알고 있는데 메모리를 다 쓰고 GC가 정리하는 시점보다 먼저 엘리스 측에서 kill proccess로 프로세스를 강제 종료하는 바람에 제대로 Collect가 안되는 것으로 보인다.
직접 System.gc()를 호출해서 통과했다.(주의할 점은 이 메서드는 소요시간이 매우 길다.)
4. 시간복잡도와 재귀호출 최대 깊이
시간복잡도는 C와 동일하게 1초에 1억번 정도의 연산으로 볼 수 있다.
재귀 호출의 최대 깊이는 안전하게는 1만 적어도 2만 이하만 가능하다.
Input/Output
생각보다 입출력을 쉽게 생각했으나, 자바의 메서드별 입출력 속도차이는 천지 차이다.
입력 -> 연산 -> 출력의 과정을 거치는 경우 연산의 시간복잡도를 아무리 계산해서 풀더라도 심하면 100만개가 넘어가는 데이터는 이미 입출력에서 1초를 넘어간다.
따라서 표준 입출력을 요하면 빠른 방법을 반드시 알아두자.
입력
입력은 크게 두 가지로 볼 수 있다. Scanner, BufferedReader.
Scanner (편한방법)
상대적으로 느리지만, 안정적(멀티스레드 안전)이고 편하다(코드가 짧다).
Scanner sc = new Scanner(System.in);
sc.next(); // 공백이나 줄바꿈 기준
sc.nextLine(); // 줄바꿈 기준
sc.nextInt(); // 바로 int반환
sc.nextLong(); // 바로 long반환BufferedReader (빠른방법)
IOException을 던질 수 있으며, java.io.*을 import 해야한다.
상대적으로 빠르다. 만약 끊어서 입력을 받으려면 StringTokenizer가 필수이다.
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
br.close(); // GC가 자동으로 메모리를 풀어주지 않으므로 직접 사용후 버퍼를 해제출력
출력도 크게 두 가지로 나눈다. System.out.print(), BufferedWriter
System.out.print (편한방법)
출력은 별거 없으나 가끔 소수점 자리수를 원하는대로 출력하려면 printf를 사용한다. StringBuilder를 적절히 사용하면 시간을 줄일 수 있다.
System.out.print();
System.out.println();
System.out.printf("%.2f", flt); // c의 printf와 비슷BufferedWriter (빠른방법)
IOException을 던질 수 있으며, java.io.*을 import 해야한다.
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); //할당된 버퍼에 값 넣어주기
String s = "abcdefg"; //출력할 문자열 (여기에 줄바꿈 문자를 넣어주면 여러줄 출력도 가능한 것.
bw.write(s+"\n"); //버퍼에 있는 값 전부 출력 직접 줄바꿈을 해줘야한다.
bw.flush(); //남아있는 데이터를 모두 출력시킴
bw.close(); //스트림을 닫음Array
주로 정적배열로는 Object[]을 동적배열로는 ArrayList를 사용한다.
// 정적 배열
int[] arr = new int[] {초기화 값};
int[] arr = new int[size];
// 동적 배열
List<Integer> arr = new ArrayList<>();
// 동적배열 삽입삭제조회
arr.add(E);
arr.remove(idx);
arr.size();
arr.get(idx);
// 배열복제 Object.clone()
int[] newArr = arr.clone();
List<Integer> arr = arr.clone();Collections의 구현체인 자료구조들을 컨테이너라고 하는데 컨테이너는 Iterator이라는 반복자로 순회하기도 함.
Iterator<T> iterator = (기존 컨테이너 이름).iterator();
// 반복자 조회 메서드
iterator.hasNext();
iterator.next();String
String에서 제공하는 여러가지 메서드들이 있다.
String 주요 메서드
String s = "test"
// 여러가지 자르기/뽑기 메서드
String[] s.split(" "); // String으로 자르기
char[] s.toCharArray(); // char[]로 분해
String s.substring(시작인덱스, 마지막인덱스(미포함)); // String 뽑기
char s.charAt(인덱스); // char 뽑기
//포함여부
boolean s.contains(문자열); // 해당문자열을 s가 포함하는지
// replace
String s.replace("기존문자열", "새로운문자열");
// 비교
boolean s.equals(String s2); // String 비교 이걸로 해야 주소가 아닌 값비교
int s.compareTo(String s2) // 사전순 대소비교
문자열 자르기
StringTokenizer을 사용하거나 String의 split을 활용할 수 있다. StringTokenizer가 빠르다. 이는 split은 정규표현식을 기반으로 동작하기 때문이다.
StringTokenizer st = new StringTokenizer(문자열, "자를 기준 문자열(생략시 공백)", "boolean 구분자도 토큰에 포함되는지 여부 true = 포함(생략시 false)");
// StringTokenizer st = new StringTokenizer(exp, "+-*", true); {"123", "+", "321"}
boolean st.hasMoreTokens(); // 토큰이 남았는지 확인
String st.nextToken(); // 다음 문자열 반환String s = "test split"
String[] tokens = s.split(" ");
// tokens = {"test", "split"}문자열 합치기
다양한 방법이 있으나 대부분 자바에서 String이 불변객체라 느린 방법이다. StringBuilder을 주로 사용하자. StringBuilder는 내부적으로 Array로 동작하기에 시간복잡도는 Array를 조작한다고 생각하면 된다.
StringBuilder sb = new StringBuilder();
sb.append(문자열); // 문자열 추가 O(1) 단순히 더하면 O(n)
sb.replace(시작인덱스, 끝인덱스, 문자열); // 특정 위치에 문자열 대체
StringBuilder sb.reverse(); // 순서 뒤집기
String sb.toString(); // String 반환
sb.delete(시작인덱스, 끝인덱스); // 시작인덱스, 종료인덱스 범위 삭제
sb.deleteCharAt(인덱스); // 문자 하나 삭제정규표현식
정규표현식을 모른다면 해당 글을 참고하자
자바에서 문자열 문제는 다루기 까다로운 편인데 정규표현식을 사용하면 코드량을 상당히 줄일 수 있다. String에서 제공하는 정규표현식 문법 중 코테에서 자주 쓰는 것만 정리한다.
// 매칭된 문자열을 모두 replacement로 변경
String replaceAll(String regex, String replacement);
// 문자열이 정규표현식에 매칭되는지 확인
boolean matches(String regex);
// 매칭되는 패턴에 맞춰 부분문자열을 배열로 반환
String[] split(String regex);Type Casting
타입변환은 자바에서 생각보다 생각해줄 것이 많다. 자바에는 원시자료형과 래퍼자료형이 있으니 구분해서 알아야한다. (자동 boxing unboxing으로 같다고 헷갈리지 말 것)
String <-> Integer
자바는 String.vauleOf와 Integer.toString 두가지 방법으로 동일하게 String을 만들 수 있다. 둘의 차이는 Null안전한지 여부이며 String.vauleOf를 실무에서 많이 쓴다고 한다.
// String -> 숫자
Integer Integer.vauleOf(String s); // 래퍼타입
int Integer.parseInt(String s); // 원시타입
// Long, Float, Double 다 동일
// 숫자 -> String
String String.valueOf(int i);
String Integer.toString(int i);
// NullPointerException만 차이가 난다.char <-> String
// String -> char
char[] String.toCharArray();
// char -> String
String.valueOf(char c);int <-> long, float <-> double
primity type 중 숫자 타입끼리는 간단하게 형변환 가능하다.
int i = 0;
long l = (long) i;
float f = 1.1;
double d = (double) f;진법변환
특이한건 String.valueOf()로는 변환이 안되는걸로 보인다.
// 진법변환
int Integer.parseInt(String s, int radix); // radix진법으로 String -> int
String Integer.toString(int v, int radix); // radix진법으로 int -> String
// Long도 메서드는 동일하다.Sort
문자열 사전순 정렬의 경우도 char 배열로 만들어서 동일하게 적용하면 된다. 물론 String.compareTo를 사용하는게 일반적으로 간단하다.
Arrays.sort(arr);
Arrays.sort(arr, comparator);
// List의 경우
Collections.sort(arr);
Collections.sort(arr, comparator);comparatable을 이용한 방법도 있는데 이건 따로 정리했다.
https://velog.io/@solfe/Comparable-VS-Comparator
Stack/Queue/Deque
보통 ArrayDeque하나로 해결한다.
// 선언
Deque<Integer> arr = new ArrayDeque<>();
// 추가
arr.addFirst(E);
arr.addLast(E);
// 삭제
arr.removeFirst();
arr.removeLast();
// 크기
arr.size();
arr.isEmpty();
// 조회
arr.peekFirst();
arr.peekLast();Map
TreeMap
레드-블랙 트리로 되어있어 키값이 정렬되어 있다. 삽입 삭제 조회가 O(log N)임이 보장된다.
// 선언
TreeMap<Key,Value> map = new TreeMap<>();
// 삽입 삭제
map.put(key, value);
map.get(key);
map.getOrDefault(key, Default value);
map.remove(key);
map.clear();
// 전체조회
Set map.keySet();
Set<Entry<Key, Value>> map.entrySet();
// Entry의 경우 이런식으로 값을 가져올 수 있음
Entry.getKey();
Entry.getValue();
// 키 소유 조회
map.containsKey(key);
// 맵이 비어있는지 조회
map.isEmpty();HashMap
hash 함수를 기반으로 탐색하며 정렬이 보장되지 않는다. 삽입 삭제 조회가 O(1)이다.
HashMap<Key, Value> map = new HashMap<> ();나머지 메서드는 동일
Set
Map이 key, value 형태였다면, Set은 집합이다.
TreeSet
마찬가지로 원소가 사전순 정렬되어 있으며 삽입 삭제 조회가 O(log N).
TreeSet<Integer> s = new TreeSet<>();
// 삽입 삭제 조회
s.add(E);
s.remove(E);
s.contains(E);
// 트리셋 전용 메서드, 모두 O(log N)
s.seiling(E); // 오름차순 기준 E보다 크거나 같은 최초의 숫자(lower bound) 반환 없다면 null
s.floor(E); // E 같거나 작은거 없다면 null
s.higer(E); // 오름차 기준 E보다 큰 최초 원소 반환 없다면 null
s.lower(E); // E보다 작은 최초 원소 반환 없다면 null
// 밑의 메서드의 경우 Priority Queue도 가능하지만 중간에 원하는 원소를 삭제하려면 TreeSet 필수.
s.first(); // 제일 작은 원소
s.last(); // 제일 큰 원소
HashSet
원소가 사전순으로 정렬되지 않으며, 삽입 삭제 조회가 O(1).
HashSet<Integer> s = new HashSet<>();
// 삽입 삭제 조회
s.add(E);
s.remove(E);
s.contains(E);혹시 두 집합을 똑같은지 비교해보고 싶다면 두 집합의 원소를 순회하며 상대 집합에 포함된 원소인지 비교하는 방법으로 가능하다.
Priority Queue
우선순위큐는 ADT의 형태로서 이를 구현하는 구현체로 힙이라고 하기도 한다.
N개의 수를 힙으로 생성하는 알고리즘은 가장 빠른 것이 O(N)이다. 그러나 보통 하나씩 삽입하여 O(N log N)으로 간단하게 쓴다.
삽입 삭제 조회의 경우 O(log N)이다.
// 기본적인 최소힙
PriorityQueue<E> pq = new PriorityQueue<>();
// int compareTo(E) 를 객체 안에 Comparable을 Override하거나, new PriorityQueue<>((o1, o2) -> o2 - o1); Comparator을 사용할 수 있다
// 삽입 삭제 조회
pq.add(E);
pq.poll(); // 삭제하고 반환
pq.peek(); // 조회
// 상태조회
pq.isEmpty(); // 비었는지 확인
pq.size(); // 크기Math
Math.pow(5, 2); // 5^2
Math.sqrt(25); // 25^(1/2)
Math.abs();
Math.floor();
Math.round();
Math.ceil();
Math.min();
Math.max();무한대
int maxVal = Integer.MAX_VALUE;
int minVal = Integer.MIX_VALUE;메서드별 시간복잡도
참고
https://drsggg.tistory.com/559
https://m.blog.naver.com/ka28/221850826909
