코테용 Java 라이브러리(자료구조) 정리

0. String ★★★★★

import java.io.*;

//BufferedReader, BufferedWriter
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

String[] strArray = br.readLine().split("");

bw.write(1+"\n");
bw.flush();
bw.close();

가장 먼저 입출력을 위해서 BufferedReader와 BufferedWriter를 사용할 수 있다. BOJ에서는 필수지만 실제 코테에서는 잘 사용하지 않음.

 

//String
String N = "a";
String K = "b";
String s = "a"+"b"; //O(N+K)
s.substring(0,1); //O(N);

//StringBuilder
StringBuilder sb = new StringBuilder();

sb.insert(0, "A"); //O(N)
sb.append("A"); //O(1)
String s = sb.toString();

> String끼리도 연산이 가능하지만, 불변 객체라는 특성상 메모리 할당을 반복하기에 성능적으로 좋지 않다. 따라서 StringBuilder나 StringBuffer클래스를 많이 이용한다. 

> 단, https://www.acmicpc.net/source/63951325와 https://www.acmicpc.net/source/63951277에서 나타난 차이를 보면 StringBuilder연산을 하고 출력하는것보다는 바로 BufferedWriter를 사용하는 것이 빠른 것 같다.

> 일반적으로 BufferedWriter보다는 StringBuilder가 시간복잡도가 빠르다. 

> StringBuilder의 insert함수는 O(N)의 시간복잡도를 갖는다.

 

 

 

 

1. ArrayList

 

import java.util.*;

//선언
ArrayList<Integer> list = new ArrayList<Integer>();
list.add(element); //O(1)
list.remove(idx); //O(n)
list.get(idx); //O(1)
list.contains(element); //O(n)

> 임시 배열을 이용하여 데이터를 저장하는 리스트. 데이터를 삭제하는 경우 배열을 순회하며 삭제 대상을 찾기때문에 O(n)의 시간복잡도를 가지지만, index로 접근하는 배열의 특성을 그대로 가지기 때문에 검색이 빠르다.

 

 

 

 

2. LinkedList

 

import java.util.*;

LinkedList<Integer> list = new LinkedList<Integer>();
list.add(element); //O(1)
list.remove(); //O(1)
list.get(index); //O(n)
list.contains(element); //O(n)

> 링크드 리스트를 이용하여 데이터를 저장. 단순히 데이터를 추가/삭제하는것은 빠르지만 원하는 데이터를 찾기 위해서는 리스트를 순회해야 해서 느리다는 리스트의 특징을 그대로 가진다. 코딩테스트에서 리스트 사용시 지금까지 내가 경험한 대부분의 케이스는 LinkedList 대신 ArrayList를 사용하는 것이 시간단축에 유리했다.

 

 

 

 

 

 

3. HashMap ★★★★★

 

import java.util.*;

HashMap<String, String> map = new HashMap<>();
map.put(key, value); //O(1)
map.get(key); //O(1)
map.containsKey(key); //O(1)
map.keySet();
map.remove(key);

Map<String, String> map = new TreeMap<>();

 

> Hashmap은 순서에 상관업이 저장되는 자료구조로, null을 허용하며 thread-safe하지 않다는 특징을 가지지만 put,get이 모두 O(1)의 시간복잡도를 가진다는 특징이 있다.

> Hashmap에 똑같은 key값을 갖는 쌍을 push하게 되면 value값이 갱신된다.

> keySet()함수의 경우 해당 map의 key들을 기반으로 한 set을 반환한다. 

 

 

이를 이용해 iter문을 사용하면 Map에서 key값들을 추출해낼 수 있는데, HashMap의 경우 순서를 보장하지 않는다. 이 경우 LinkedHashMap을 사용해야 순서를 보장한다.

+ TreeMap의 경우 key를 기준으로 binary search tree(b-tree 등)로 구현되어 있다.

 (참고: https://codingdog.tistory.com/entry/java-map-set-%EC%88%9C%ED%9A%8C%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95%EC%9D%84-%EA%B0%84%EB%8B%A8%ED%95%98%EA%B2%8C-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4)

 

 

 

 

4. HashSet

 

import java.util.*;

HashSet<Integer> set = new HashSet<>();
set.add(element); //O(1)
set.remove(element); //O(1)
set.contains(element); //O(1)
set.toArray(new Object[0]); //매개변수로 길이0짜리 배열 타입정보

Set<Integer> set = new Treeset<>();

> HashSet의 경우 객체들을 순서와 중복 없이 저장한다.

> null인 element를 허용한다.

+ Treeset의 경우 binary search tree(b-tree 등)로 구현되어 있다.

 

 

 

 

5. PriorityQueue

 

import java.util.*;

PriorityQueue<Integer> queue = new PriorityQueue<>(); //오름차순 (작은수 우선순위 높음)
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder()); //내림차순
queue.add(n); //O(logn)
queue.peek(); //O(1)
queue.poll(); //O(logn)
queue.size(); //O(1)

> Heap을 사용한 자료구조

> PriorityQueue의 경우 인자에 우선순위를 지정해줄 수 있다.

> 우선순위 기준은 객체의 compare함수를 @override하거나, Comparator의 compare함수를 @override함으로서 커스텀할 수 있다.

(i1-i2: 작은값 우선, 참고: https://eckrin.tistory.com/36)

 

 

 

 

6. Deque (Double-ended Queue)

 

import java.util.*;

Deque<String> deque = new ArrayDeque<>();
Deque<String> deque = new LinkedList<>();
deque.addFirst("a"); //O(1)
deque.addLast("b"); //O(1)
deque.removeFirst(); //O(1)
deque.removeLast(); //O(1)

> Deque은 간단하게 얘기해서 앞뒤로 삽입/삭제가 가능한 큐라고 할 수 있다.

> Deque는 구현체에 따라 ArrayDeque, LinkedList의 구현체로 나타낼 수 있다.

> LinkedList 구현체를 사용하는 것보다 ArrayDeque를 사용하는 것이 메모리 관리에 유리한 듯 보인다. (배열 크기를 동적으로 증가시키기 위해 남는 배열의 크기보다, 포인터가 잡아먹는 메모리가 더 큰것으로 보임 - https://www.acmicpc.net/source/81262516)

 

 

 

 

7. Stack

 

import java.util.*;

Stack<Integer> stack = new Stack<>();
stack.push(n); //O(1)
stack.pop(); //O(1)
stack.size(); //O(1) //Vector는 동적배열이므로 O(1)로 추정
stack.empty();
stack.contains(1); //O(n)

stack.get(i); //vector 활용, O(1)로 추정

> dfs와 연관이 깊은 자료구조

> java.util에서 제공하는 Stack클래스는 내부에서 Vector를 사용하는 것 같다.

 

 

 

 

8. Queue

 

import java.util.*;

Queue<Integer> queue = new LinkedList<>();
queue.add(n); //O(1)
queue.poll(); //O(1)
queue.peek(); //O(1)
queue.size(); //O(n) (linkedList이므로)
queue.empty();
queue.contains(1); //O(n)

> Stack과 다르게 전용 구현체가 존재하지 않는다. LinkedList를 구현체로 사용할 수 있다.

 

 

 

9. BinarySearch

int[] arr; //정렬된 배열
int idx = Arrays.binarySearch(arr, 3); //배열에서 3을 이진탐색으로 찾음
//값이 존재한다면 인덱스 반환
//존재하지 않으면 그 값을 끼워넣었을때 1부터 시작하는 인덱스의 음수값

 

 

 

 

 

잡기술

 

1. 시간 계산

- 초(s)와 같이 작은 단위로 환산하기

 

예시) 프로그래머스 - 호텔 대실

class Solution {
    static final int DAY=60*24+10+1; //하루+청소시간
    ...
    public int solution(String[][] book_time) {
            ...
            arr[start_h*HOUR+start_m]++;
            arr[end_h*HOUR+end_m+10]--;
            ...
    }
}

 

 

2. 수 자릿수 구하기

 

- String으로 구하기

: char배열로 받은다음 int배열에 '0'을 빼는 방식으로 환산해주면 된다.

 

예시) BOJ 1427 소트인사이드

static String N;
static Integer[] arr;
public static void main(String[] args) throws IOException {
        ...
        N = br.readLine();
        arr = new Integer[N.length()];
        for(int i=0; i<N.length(); i++) {
            arr[i] = N.charAt(i)-'0';
        }
        Arrays.sort(arr, Collections.reverseOrder());
}

 

 

3. 배열/컬렉션 비교

https://eckrin.tistory.com/36

return a-b가 오름차순, return b-a가 내림차순인거 기억하기.

비슷하게 return strA.compareTo(strB)가 오름차순, return strB.compareTo(strA)가 내림차순이다.

 

 

 

 

주의할것

 

 

1. 배열 선언시

-> 선언 자체로도 그 크기만큼의 시간복잡도를 가진다. 아래 반복문은 O(N*M*N*M)의 시간복잡도를 가짐.

for(int i=0; i<N; i++) {
    for(int j=0; j<M; j++) {
        visited = new boolean[N][M]; //**주의** 선언자체로도 해당 크기만큼의 시간복잡도를 가진다.
        ...
    }
}