[코딩테스트] Java - 자료구조

배열

- 배열: 같은 자료형의 묶음. 크기가 고정

- ArrayList: 같은 자료형의 묶음 크기가 동적

배열

/* 1차원 배열 */
type[] arrName = new type[count]; // 배열 선언 및 0으로 초기화
type[] arrName = {value1, ...}; // 배열 선언 및 초기화

arrName[index]; // 배열값 조회

arrName.length; // 배열의 길이

Arrays.sort(arrName); // 배열의 데이터를 정렬

Arrays.toString(arrName); // 배열의 모든 데이터를 String으로 변환

/* 2차원 배열 */ 
type[][] arrName = new type[rows][columns]; // 배열 선언 및 0으로 초기화
type[][] arrName = {{value1, ...}, {value2, ...}, ...}; // 배열 선언 및 초기화

arrName[arr_index][column_index]; // 배열값 조회

 

ArrayList

ArrayList<ReferenceType> list = new ArrayList<>();
ArrayList<ReferenceType> list = new ArrayList<>(list);

list.add(value); // 리스트 맨뒤 값 추가

list.get(index); // 해당 인덱스의 값에 접근

list.remove(index); // 해당 인덱스의 값 삭제. O(N)

list.size(); // 데이터의 개수

list.isEmpty(); // 비어있는지 여부 확인

Collections.sort(list); // 정렬

 

예시

배열 정렬

public class Main {
    private static int[] solution(int[] arr) {
        int[] clone = arr.clone(); // 배열을 복사하여 새로운 배열 생성
        Arrays.sort(clone);  // 원본 배열 자체를 정렬
        return clone;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 7, 2, 8, 3};
        int[] sortedArr = solution(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(sortedArr));
    }
}

배열 중복값 제거후 내림차순 정렬

- Arrays 클래스의 stream()은 stream으로 변환. stream의 Primitive Type인 IntStream의 데이터를 boxed()로 Integer로 변환하고 distinct()를 통해 중복 제거 후 Integer형 배열로 중복 제거된 데이터를 반환

- distinct()는 O(N)을 보장

import java.util.Arrays;
import java.util.Collections;

public class Main {
    private static int[] solution(int[] arr) {
        // 중복값 제거
        Interger[] result = Arrays.stream(arr).boxed().distinct().toArray(Integer[]::new);
        Arrays.sort(result, Collections.reverseOrder()); // 내림차순 정렬
        // int형 배열로 변환
        return Arrays.stream(result).mapToInt(Integer::intValue).toArray();
    }
}

스택

- FILO(First In Last Out) 구조

import java.util.*;

/* Stack */
Stack<Integer> stack = new Stack<>();
stack.push(val);  // 원소 삽입
stack.pop();      // 가장 최근에 삽입된 원소 반환 및 삭제
stack.peek();     // 가장 최근에 삽입된 원소
stack.isEmpty();  // 원소가 없다면 true 반환
stack.size();     // 원소 개수

 

큐

- FIFO(First In First Out) 구조

import java.util.*;

/* Queue */
Queue<String> q = new LinkedList<>();
q.offer(val);    // 원소 삽입
q.poll();        // 가장 먼저 삽입된 원소 반환 및 삭제
q.peek();        // 가장 먼저 삽입된 원소
q.isEmpty()      // 비어있다면 true 반환
q.size();        // 원소 개수

/* ETC */
q.add(val);    // q.offer(val)와 비슷하지만 예외 발생
q.remove();    // q.poll()과 비슷하지만 예외 발생
q.element();   // q.peek()와 비슷하지만 예외 발생

 

덱

- FIFO + FILO 구조로 양방향으로 삽입/방출

import java.util.*;

/* Deque */
ArrayDeque<Character> dq = new ArrayDeque<>();
dq.offerFirst(val); // 맨 앞에 값 삽입
dq.offerLast(val);  // 맨 뒤에 값 삽인
dq.pollFirst();     // 맨 앞의 값 반환 및 삭제
dq.pollLast();      // 맨 뒤의 값 반환 및 삭제
dq.peekFirst();     // 맨 앞의 값 반환
dq.peekLast();      // 맨 뒤의 값 반환
dq.isEmpty();    // 비어있다면 true 반환
dq.size();       // 원소 개수
dq.contains(val) // 해당 값 포함시 true 반환

/* ETC */
dq.addFirst(val); // dq.offerFirst()와 비슷하지만 예외 발생
dq.addLast(val);  // dq.offerLast()와 비슷하지만 예외 발생
dq.removeFirst(); // dq.pollFirst()와 비슷하지만 예외 발생
dq.removeLsat();  // dq.pollLast()와 비슷하지만 예외 발생
dq.getFirst();    // dq.peekFirst()와 비슷하지만 예외 발생
dq.getLast();     // dq.peekLast()와 비슷하지만 예외 발생

 

해시

- Key와 Value 형태의 데이터 구조

import java.util.*;

/* HashMap */
HashMap<String, Integer> map = new HashMap<>();
map.put(key, val);                  // 키가 없다면 새로 생성하여 추가, 키가 존재한다면 값 수정
map.getOrDefault(key, defaultVal);  // 키가 없다면 defaultVal 반환, 키가 존재한다면 해당 값 반환
map.remove(key);                    // 키값을 제거하고 value 반환
map.remove(key, val);               // 키와 값을 제거하고 true 반환
map.containsKey(key);               // key가 포함되어있다면 true 반환
map.contains.Value(val);            // value가 포함되어 있다면 true
map.isEmpty();                      // 비어있다면 true
map.size();                         // 원소 개수


/* ETC */
map.get(key);    // key에 해당하는 값 반환. key가 없는 경우 에러 발생 
map.entrySet();  // Set 형태로 Entry 반환
map.keySet();    // 키값들을 Set으로 반환
map.values();    // collection 형태로 반환

 

집합

- 중복된 값이 없는 데이터 모음

import java.util.*;

/* Set */
HashSet<Integer> set = new HashSet<>();
set.add(val);       // 값 추가
set.remove(val);    // 값 제거
set.isEmpty();      // 비어있다면 true 반환
set.size();         // 원소 개수
set.contains(val);  // 값 포함시 true 반환


/* ETC */
set.equals(set);  // 동일한 set일 경우 true 반환

 

트리

- 

 

 

그래프

-