Collections의 의미와 종류

  • Collections란?
    • 자주 쓰는 자료구조로 이미 Java 언어 내부 Collections에 구현되어 있음
  • Collections의 종류는?
    • Vector
    • Deque
    • List
    • Set
    • Map
    • Stack
    • Queue
    • ...

ArrayList (java.util.ArrayList< E>)

  • java.long.Object

    • java.util.AbstractCollection< E>
      • java.util.AbstractList< E>
        • java.util.ArrayList< E>
          public class ArrayList<E>
          extends AbstractList<E>
          implements List<E>, RandomAccess, Cloneable, Serializable
  • 길이가 변하는 배열

  • C++에서는 Vector에 해당하는 역할

  • 공식 문서

  • ArrayList의 생성 방법

    • ArrayList()
      • 단순 생성
    • ArrayList(int initialCapacity)
      • 초기의 크기를 정해줄 수 있음
  • ArrayList를 사용할 때 많이 사용하는 메소드

    • boolean add(E e)
      • ArrayList의 뒤에 새로운 Element를 추가하는 것
      • O(N)의 시간이 걸림
    • void add(int index, E element)
      • Index번째에 추가하는 것
    • void clear()
      • ArrayList를 완전히 비워버리는 것
      • O(N)의 시간이 걸림
    • boolean Contains(Object o)
      • 어떠한 Object o가 들어있는지 판단
    • E get(int index)
      • Index번째를 데려오는 메소드
    • boolean isEmpty()
      • 비어있는지 확인하는 것
    • E remove(int index)
      • 특정 index의 Element를 지우는 것
      • O(N)의 시간이 걸림
    • E set(int index, E element)
      • 특정 index의 Element를 새로운 Element로 재배정하는 것
    • Object[] toArray()
      • ArrayList를 Array로 바꿈
  • ArrayList의 사용 예 1

    • 수 정렬하기 (https://www.acmicpc.net/problem/2750)
      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);  
        }
      }
      }
  • ArrayList의 사용 예 2

    ArrayList<Integer>[] a = (ArrayList<Integer>[]) new ArrayList[n+1];
    // ArrayList의 배열 만들기

    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);
    }

LinkedList (java.util.LinkedList< E>)

  • 이중 연결 리스트
  • java.lang.Object
    • java.util.AbstractCollection< E>
      • java.util.AbstractList< E>
        • java.util.AbstractSequentialList< E>
          • java.util.LinkedList< E>
  • 공식 문서
  • C++에서 List와 같은 역할
  • 실제 프로그래밍 대회에서는 많이 쓰이지 않는다.

Stack (java.util.Stack< E>)

  • 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조
  • 마지막으로 넣은 것이 가장 먼저 나오기 때문에 Last In First Out (LIFO)라고도 한다.
  • E push(E item)
    • push: 스택에 자료를 넣는 연산
  • E pop()
    • pop: 스택에서 자료를 빼는 연산
  • E peek()
    • top: 스택의 가장 위에 있는 자료를 보는 연산
  • bool empty()
    • empty: 스택이 비어있는지 아닌지를 알아보는 연산
  • int size()
    • size: 스택에 저장되어 있는 자료의 개수를 알아보는 연산
  • C++의 Stack과의 가장 큰 차이점은 Return 값의 유무
    • Java는 리턴 값이 있음
    • C++은 리턴 값이 없음
  • 공식 문서

Set (java.util.Set< E>)

  • 인터페이스이다.
  • 중복된 원소를 포함하지 않는다.
  • Set을 구현한 라이브러리
    • HashSet
    • TreeSet
    • LinkedHashSet
  • 공식 문서
  • Set의 기본 메소드
    • boolean add(E e)
    • void clear()
    • boolean contains(Object o)
    • boolean isEmpty()
    • boolean remove(Object o)
    • int size()
    • Object[] toArray()
      • STL의 경우 시간 복잡도가 모두 log(n)으로 고정
      • Java의 경우 어떻게 구현된 것을 사용하냐에 따라 시간 복잡도가 변화

HashSet (java.util.HashSet< E>)

  • java.lang.Object
    • java.util.AbstractCollection< E>
      • java.util.AbstractSet< E>
        • java.util.HashSet< E>
  • 공식 문서
  • HashTable을 이용해서 구현
  • 삽입/삭제/제거 연산의 시간 복잡도가 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.println(x + " "); // 순서대로 출력이 보장되지 않는다.
        }
      }
      }

TreeSet (java.util.TreeSet< E>)

  • java.lang.Object
    • java.util.AbstractCollection< E>
      • java.util.AbstractSet< E>
        • java.util.TreeSet< E>
  • 공식 문서
  • STL의 Set과 거의 같은 역할
  • 이진 검색 트리 (레드 블랙 트리)를 이용해서 구현되어 있다.
  • 삽입/삭제/제거 연산의 시간 복잡도가 O(lgN)이다.
  • (오름차, 내림차) 순서가 보장된다.
    • 가장 큰 장점임
    • 넣는 순서가 아닌 Comparable에 따라 내림차, 오름차 등이 보장됨
      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) {
          System.out.println(x + " ");  
        }
      }
      }

LinkedHashSet (java.util.LinkedHashSet< E>)

  • java.lang.Object
    • java.util.AbstractCollection< E>
      • java.util.AbstractSet< E>
        • java.util.LinkedHashSet< E>
  • 공식 문서
  • 삽입/삭제/제거 연산의 시간 복잡도가 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) {
            System.out.println(x + " ");  
          }
        }
      }

Set의 선택

  • 일반적인 경우 HashSet
  • (오름차, 내림차) 순서가 중요한 경우 TreeSet (line sweeping algorithm)
  • 입력한 순서가 중요한 경우 LinkedHashSet
  • Set의 예제
    • 숫자카드 문제 (https://www.acmicpc.net/problem/10815)
      • 순서가 중요하지 않다.
        • 즉, HashSet을 사용하는 것이 유리하다.
          • 각 구현 Set의 결과
        • HashSet: 764MS
        • TreeSet: 1028MS
        • LinkedHashSet: 832MS

Map

  • Set과 같이 Interface임
  • 중복된 Key를 포함하지 않는다.
  • (Key, Value) 쌍을 이룬다. (사전과 비슷)
  • Map을 구현한 것
    • HashMap
    • TreeMap
      • RedBlack Tree를 이용
    • LinkedHashMap
  • 주요 Method
    • 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에 해당하는 Value Return
    • boolean isEmpty()
      • 비어있는지 확인
    • Set< K> key keySet()
      • Key를 이용해 Set을 만들어줌
    • V put(K key, V value)
      • Key, Value 쌍을 넣을 수 있음
    • boolean remove(Object o)
      • 해당하는 Key를 Remove
    • int size()
      • Size Return
  • 사용 예
    • 듣도보도 못한 사람 찾기 (https://www.acmicpc.net/problem/1764)
    • TreeMap을 이용한 풀이
      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.util.*;
      public class Main {
        public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            TreeMap<String, Integer> d = new TreeMap<String, Integer>();
            for (int i=0; i<n; i++) { // 듣도 못한 사람 추가
                String name = br.readLine();
                d.put(name, 1);
            }
            for (int i=0; i<m; i++) { // 보도 못한 사람 + 2
                                        // 이미 듣도 못한 사람이었으면 3
                String name = br.readLine();
                Integer v = d.get(name);
                if (v == null) {
                    v = 0;
                }
                v += 2;
                d.put(name, v);
            }
            ArrayList<String> a = new ArrayList<String>();
            for (Map.Entry<String, Integer> entry : d.entrySet()) {
                String key = entry.getKey();
                Integer value = entry.getValue();
                if (value == 3) {
                    a.add(key);
                }
            }
            System.out.println(a.size());
            for (String name : a) {
                System.out.println(name);
            }
        }
      }
    • HashMap을 이용한 풀이
      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      import java.util.*;
      public class Main {
        public static void main(String args[]) throws IOException{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] line = br.readLine().split(" ");
            int n = Integer.parseInt(line[0]);
            int m = Integer.parseInt(line[1]);
            TreeMap<String, Integer> d = new HashMap<String, Integer>();
            for (int i=0; i<n; i++) { // 듣도 못한 사람 추가
                String name = br.readLine();
                d.put(name, 1);
            }
            for (int i=0; i<m; i++) { // 보도 못한 사람 + 2
                                        // 이미 듣도 못한 사람이었으면 3
                String name = br.readLine();
                Integer v = d.get(name);
                if (v == null) {
                    v = 0;
                }
                v += 2;
                d.put(name, v);
            }
            ArrayList<String> a = new ArrayList<String>();
            for (Map.Entry<String, Integer> entry : d.entrySet()) {
                String key = entry.getKey();
                Integer value = entry.getValue();
                if (value == 3) {
                    a.add(key);
                }
            }
            System.out.println(a.size());
              Collections.sort(a);
            for (String name : a) {
                System.out.println(name);
            }
        }
      }
    • 시간 복잡도를 잘 계산하여 효과적으로 하는 것이 좋다.
    • 계속 큰 시간복잡도를 가진 삽입을 사용하는 것이 나은가 vs 한번 정렬하는 시간복잡도를 사용하는 것이 나은가
    • 이 경우에는 HashSet이 대량의 데이터 삽입에 있어서 효율이 좋았던 것 같음았다
    • HashSet으로 Map을 만든 후에 한번 정렬해주는 것이 더 좋았다

Queue

  • Java에서 Queue는 Interface로 구현되어 있다.
  • 공식 문서
  • Queue를 구현한 클래스는 다음과 같다.
    • ArrayDeque
    • LinkedList
    • PriorityQueue
      • 위의 것과는 다른 방식의 큐이다.
      • 최대값 또는 최소값이 우선순위를 갖고 그것이 먼저 나오는 큐
  • 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
  • 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out (FIFO) 라고도 한다.
  • 대표 메소드
    • push: boolean offer(E e)
      • 큐에 자료를 넣는 연산
    • pop: E poll()
      • 큐에서 자료를 빼는 연산
      • C++에서는 Return을 하지 않는다.
    • front: E peek()
      • 큐의 가장 앞에 있는 자료를 보는 연산
    • back: (java에는 존재하지 않는다.)
      • 큐의 가장 뒤에 있는 자료를 보는 연산
    • empty: boolean isEmpty()
      • 큐가 비어있는지 아닌지를 알아보는 연산
    • size: int size()
      • 큐에 저장되어 있는 자료의 개수를 알아보는 연산

PriorityQueue

  • 크기가 가장 작거나 큰 것부터 pop이 되는 queue를 말한다.
  • 최대 Heap이나 최소 Heap을 이용하여 구현하는 경우가 많다.
  • java.lang.Object
    • java.util.AbstractCollection< E>
      • java.util.AbstractQueue< E>
        • java.util.PriorityQueue< E>
  • 공식 문서
  • 예제
    • PriorityQueue를 이용한 최소 힙 문제의 구현
      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); 
          }
        }
      }
      }
    • PriorityQueue를 이용한 최대 힙 문제의 구현
      public class Main {
      static class Compare implements Comparator<Integer> {
        public int compare(Integer one, Integer two) P
          return two.compareTo(one); 
        }
      }
      public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        Compare cmp = new Compare();
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(1, cmp);
        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); 
          }
        }
      }
      }