Algorithm Study With Java #2 (JAVA COLLECTIONS)

jakeseo_me·2019년 2월 11일
0

java algorithm study

목록 보기
2/18

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>
  • 길이가 변하는 배열
  • C++에서는 Vector에 해당하는 역할
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html
  • 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)
  • ArrayList의 사용 예 2
    - 그래프 문제의 인접 리스트 만들기에 가장 많이 사용한다.

LinkedList (java.util.LinkedList< E>)

  • 이중 연결 리스트
  • java.lang.Object
    - java.util.AbstractCollection< E>
    - java.util.AbstractList< E>
    - java.util.AbstractSequentialList< E>
    - java.util.LinkedList< E>
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html
  • 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++은 리턴 값이 없음
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

Set (java.util.Set< E>)

  • 인터페이스이다.
  • 중복된 원소를 포함하지 않는다.
  • Set을 구현한 라이브러리
    - HashSet
    • TreeSet
    • LinkedHashSet
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/Set.html
  • 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>
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html
  • HashTable을 이용해서 구현
  • 삽입/삭제/제거 연산의 시간 복잡도가 O(1)이다.
  • 순서가 보장되지 않는다.
    - 집합이 필요한데 순서가 보장될 필요가 없는 경우에 사용

TreeSet (java.util.TreeSet< E>)

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

LinkedHashSet (java.util.LinkedHashSet< E>)

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.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 a = new ArrayList();
      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을 이용한 풀이
    • 시간 복잡도를 잘 계산하여 효과적으로 하는 것이 좋다.
    • 계속 큰 시간복잡도를 가진 삽입을 사용하는 것이 나은가 vs 한번 정렬하는 시간복잡도를 사용하는 것이 나은가
    • 이 경우에는 HashSet이 대량의 데이터 삽입에 있어서 효율이 좋았던 것 같음았다
    • HashSet으로 Map을 만든 후에 한번 정렬해주는 것이 더 좋았다

Queue

  • Java에서 Queue는 Interface로 구현되어 있다.
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html
  • 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>
  • 공식 문서
    - https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html
  • 예제
    - PriorityQueue를 이용한 최소 힙 문제의 구현
    • PriorityQueue를 이용한 최대 힙 문제의 구현
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글