백준 강의 정리 - Collections

Collections의 Stack, Queue 등을 사용하면 구현 없이 사용할 수 있다.

boolean add(E e)
- 새로운 element e를 추가
void add(int index, E element)
- O(n)
- index번째에 새로운 element e를 추가
void clear()
- ArrayList를 완전히 비움
boolean Contains(Object o)
- O(n)
- Object o가 들어있는지 아닌지를 판단
E get(int index)
- index번째를 데려옴
- arr[index]는 arr.get와 같은 표현이다.
boolean isEmpty()
- ArrayList가 비어있는지 아닌지 판단
E remove(int index)
- O(n)
- index번째 삭제
E set(int index, E element)
- index번째를 새로운 element로 바꿈
- arr[index] = element와 같다
Object[] toArray()
- Array로 바꾸기

1.2 예제

ArrayList에 element 넣어서 출력하기

import java.util.*;
public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    ArrayList<Integer> a = new ArrayList<Integer>();
    for (int i=0; i<n; i++) {
      int temp = sc.nextInt();
      a.add(temp);
    }
    // 정렬하기
    Collections.sort(a);
    for (int x : a) {
      System.out.println(x);
    }
    // 이렇게도 출력 가능
    // for (int i=0; i<n; i++) {
    //   System.out.println(a.get(i));
    // }
  }
}

그래프 문제의 인접 리스트 만들기

ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];

for (int i=1; i<=n; i++) {
    a[i] = new ArrayList<Integer>();
}
for (int i=0; i<m; i++) {
    int u = sc.nextInt();
    int v = sc.nextInt();
    // 인접한 간선 만들기
    a[u].add(v);
    a[v].add(u);
}

2. LinkedList

이중 연결 리스트라고 한다.
java.util에 들어있다.
대회 문제나 알고리즘 문제에서는 사용하는 경우가 드물다.

3. Stack

java.util에 들어있다.
가장 많이 사용하는 메소드 중 하나이다.
한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조이다.
마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out(LIFO)라고도 한다.

3.1 Stack의 주요 메소드

E push(E item)
- 스택에 자료를 넣는 연산
E pop()
- 스택에서 자료를 빼는 연산
- return값이 있다 (C++에서는 없음)
E peek()
- 스택의 가장 위에 있는 자료를 보는 연산
bool empty()
- 스택이 비어있는지 아닌지를 알아보는 연산
int size()
- 스택에 저장되어있는 자료의 개수를 알아보는 연산

4. Set

인터페이스이다.
중복된 원소를 포함하지 않는다.
Set을 구현한 것으로 HashSet, TreeSet, LinkedHashSet이 있다.
일반적인 경우에는 HashSet을 사용하고, 순서가 중요한 경우에는 TreeSet, 입력으로 넣은 순서가 중요한 경우에는 LinkedHashSet을 사용한다.

4.1 Set의 주요 메소드

boolean add(E e)
- 새로운 element e를 추가
void clear()
- Set을 완전히 비움
boolean contains(Object o)
- Object o가 들어있는지 아닌지를 판단
boolean isEmpty()
- Set이 비어있는지 아닌지 판단
boolean remove(Object o)
- Object o 삭제
int size()
- Set 크기 알아보기
Object[] toArray()
- Array로 바꾸기

4.2 HastSet

해시 테이블을 이용해서 구현되어 있다.
삽입/삭제/제거 연산의 시간 복잡도가 O(1)이다.
순서가 보장되지 않는다.

import java.util.*;
public class Main {
  public static void main(String args[]) {
    HashSet<Integer> d = new HashSet<Integer>();
    for (int i=10; i>=1; i--) {
      d.add(i); 
    }
    for (int x : d) {
      // 순서를 모른다.
      System.out.print(x + " ");
    }
  }
}

4.3 TreeSet

이진 검색 트리(레드 블랙 트리)로 이루어져 있다.
삽입/삭제/제거 연산의 시간 복잡도가 O(log N)이다.
순서가 보장된다.

import java.util.*;
public class Main {
  public static void main(String args[]) {
    TreeSet<Integer> d = new TreeSet<Integer>();
    for (int i=10; i>=1; i--) {
      d.add(i); 
    }
    for (int x : d) {
      // 1 2 3 4 5 6 7 8 9 10
      System.out.print(x + " ");
    }
  }
}

4.4 LinkedHashSet

해시테이블과 연결리스트를 이용해서 구현되어 있다.
삽입/삭제/제거 연산의 시간 복잡도가 O(1)이다.
추가한 순서가 보장된다.

import java.util.*;
public class Main {
  public static void main(String args[]) {
    LinkedHashSet<Integer> d = new LinkedHashSet<Integer>();
    for (int i=10; i>=1; i--) {
      d.add(i);
    }
    for (int x : d) {
      // 10 9 8 7 6 5 4 3 2 1
      System.out.print(x + " ");
    }
  }
}

5. Map

인터페이스이다.
중복된 Key를 포함하지 않는다.
Key-Value 쌍을 이룬다. (사전과 비슷)
Map을 구현한 것으로 HashMap, TreeMap, LinkedHashMap이 있다.

5.1 Map의 주요 메소드

void clear()
- Map을 완전히 비움
boolean containsKey(Object key)
- key가 들어있는지 아닌지 확인
boolean containsValue(Object value)
- 어떤 value를 가지고있는지 아닌지를 확인
Set<Map.Entry<K,V>> entrySet()
- Key-Value 쌍을 이용한 Set을 만들어줌
V get(Object key)
- Key를 넣으면 Key에 해당하는 Value 리턴
boolean isEmpty()
- Map이 비어있는지 아닌지 판단
Set
keySet()
- Key를 이용해서 만든 Set을 만들어줌
V put(K key, V value)
- Key에 해당하는 Value를 넣음
boolean remove(Object o)
- Object o 삭제
int size()
- Map의 크기 알아보기

6. Queue

한쪽 끝에만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조.
먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out(FIFO)라고도 한다.
인터페이스이다.
구현한 클래스로는 ArrayDeque, LinkedList, PriorityQueue가 있다.
뒤에 무슨 데이터가 있는지 알아보는 메소드는 존재하지 않는다. 중요하지 않기 때문이다.

6.1 Queue의 주요 메소드

boolean offer(E e)
- 큐에 자료를 넣는 연산(push)
E poll()
- 큐에서 자료를 빼는 연산(pop)
- return값이 있다 (C++에서는 없음)
E peek()
- 큐의 가장 앞에 있는 자료를 보는 연산
bool isEmpty()
- 큐가 비어있는지 아닌지를 알아보는 연산
int size()
- 큐에 저장되어있는 자료의 개수를 알아보는 연산

6.2 PriorityQueue

우선 순위 큐라고 한다.
큐에 들어있는 아이템들 중 우선순위가 높은 아이템부터 pop이 된다.
최대 힙이나 최소 힙으로 구현하게 되는 경우가 많다.

//최소 힙을 구하는 소스
import java.util.*;

public class Main {
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    PriorityQueue<Integer> q = new PriorityQueue<Integer>();
    int n = sc.nextInt();
    while (n-- > 0) {
      int x = sc.nextInt();
      if (x == 0) {
        if (q.isEmpty()) {
          System.out.println(0);
        } else {
          System.out.println(q.poll());
        }
      } else {
        q.offer(x);
      }
    }
  }
}

[JAVA] 프로그래밍 대회에서 사용하는 자바 - 2

목차

1. ArrayList

1.1 ArrayList의 주요 메소드

1.2 예제

2. LinkedList

3. Stack

3.1 Stack의 주요 메소드

4. Set

4.1 Set의 주요 메소드

4.2 HastSet

4.3 TreeSet

4.4 LinkedHashSet

5. Map

5.1 Map의 주요 메소드

6. Queue

6.1 Queue의 주요 메소드

6.2 PriorityQueue