180520.md

July 26, 2018 · View on GitHub

정렬

관련 문제들

[issue]에 대한 정리

[#issue1] Comparable, Comparator 을 이용한 Java 객체 정렬

* 객체를 사용자가 정의한 정렬 기준에 맞춰 정렬하는 방법
    Ex) 좌표를 x좌표가 증가하는 순, x좌표가 같으면 y좌표가 감소하는 순으로 정렬
    Ex) 국어점수는 증가하는 순, 수학점수는 감소하는 순으로 정렬
* 객체의 정렬 기준을 명시하는 두 가지 방법
1. Comparable interface 구현
    * 정렬할 객체에 Comparable interface를 implements 후 compareTo() 메소드를 오버라이드
    * compareTo() 메소드는 현재 객체가 파라미터로 넘어온 객체보다 작으면 음수 리턴, 같으면 0 리턴, 크면 양수 리턴 하도록 작성
    * Collections.sort(list)
2. Comparator interface 구현
    * Collections.sort() 메소드는 두 번째 인자로 Comparator interface를 받을 수 있음
    * Comparator interface를 implements 후 compare() 메소드를 오버라이드한 myComparator class 작성
    * compareTo() 메소드는 첫 번째 파라미터로 넘어온 객체가 두 번째 파라미터로 넘어온 객체보다 작으면 음수 리턴, 같으면 0 리턴, 크면 양수 리턴 하도록 작성
    * Collections.sort(list, myComparator)

[#issue1-1] Comparable, Comparator 사용 예제

  1. Comparable
class Point implements Comparable<Point> {
    int x, y;

    @Override
    public int compareTo(Point p) {
        if(this.x > p.x) {
            return 1;
        }
        else if(this.x == p.x) {
            if(this.y > p.y) {
                return 1;
            }
        }
        return -1;
    }
}

// main에서 사용법
List<Point> pointList = new ArrayList<>();
pointList.add(new Point(x, y));
Collections.sort(pointList);
  1. Comparator
class MyComparator implements Comparator<Point> {
    @Override
    public int compare(Point p1, Point p2) {
        if (p1.x > p2.x) {
            return 1;
        }
        else if (p1.x == p2.x) {
            if (p1.y > p2.y) {
                return 1;
            }
        }
        return -1;
    }
}

// main에서 사용법
List<Point> pointList = new ArrayList<>();
pointList.add(new Point(x, y));
MyComparator myComparator = new MyComparator();
Collections.sort(pointList, myComparator);

[#issue2] Java 언어를 이용하여 정렬할 때 시간초과 문제

* Scanner 대신에 BufferedReader, BufferedWriter를 사용해야 하는 이유
* Scanner
    * 사용이 간단. 속도가 느림. Buffer 사이즈: 1024 chars
* BufferedReader
    * 사용이 조금 복잡. 속도가 비교적 빠름. Buffer 사이즈: 8192 chars
* 많은 입력이 있다면 성능상 우위에 있는 BufferedReader를 사용한다.
* 기본적으로는 간단한 Scanner를 사용한다.

[#issue3] List와 ArrayList의 차이

* List
    * 인터페이스, 다형성을 지원한다.
* ArrayList
    * 구현클래스

[#issue3-1] 업캐스팅, 다운캐스팅이란

* 업캐스팅
    * 부모 클래스 = 자식 클래스
* 다운캐스팅
    * 업캐스팅 한 것을 다시 원래의 형으로 변환하는 것

[#issue4] Arrays.sort()와 Collections.sort()의 차이

* Arrays.sort()
    * Object Array에서는 TimSort(Merge Sort + Insertion Sort)를 사용
        * Object Array: 새로 정의한 클래스에 대한 배열
    * Primitive Array에서는 Dual Pivot QuickSort(Quick Sort + Insertion Sort)를 사용
        * Primitive Array: 기본 자료형에 대한 배열 
* Collections.sort()
    * 내부적으로 Arrays.sort()를 사용

[#issue5] BufferedReader/BufferedWriter, InputStreamReader/OutputStreamWriter의 차이

* InputStreamReader
    * character(키보드로 입력하는 글자 한 개) 단위로 입력받는다.
* BufferedReader
    * character가 아닌 줄단위의 문자열을 입력받는다.
    * InputStreamReader에 버퍼링 기능(Buffer 사이즈: 8192 chars)을 추가한 것
    * 속도를 향상시키고 시간의 부하를 줄일 수 있다.
    * 문자(character) 단위로 처리
* BufferedInputStream
    * 바이트(byte) 단위로 처리
* bw.flush()의 용도?
    * 버퍼의 모든 내용을 지운다.

[#issue6] String, StringBuilder, StringBuffer의 차이

* String
    * 새로운 값을 할당할 때마다 새로 클래스에 대한 객체가 생성된다.
    * String에서 저장되는 문자열은 private final char[]의 형태이기 때문에 String 값은 바꿀수 없다.
        * private: 외부에서 접근 불가
        * final: 초기값 변경 불가
    * String + String + String... 
        * 각각의 String 주솟값이 Stack에 쌓이고, Garbage Collector가 호출되기 전까지 생성된 String 객체들은 Heap에 쌓이기 때문에 메모리 관리에 치명적이다.
    * String을 직접 더하는 것보다는 StringBuffer나 StringBuilder를 사용하는 것이 좋다.
* StringBuilder, StringBuffer
    * memory에 append하는 방식으로, 클래스에 대한 객체를 직접 생성하지 않는다.
    * StringBuilder
        * 변경가능한 문자열
        * 비동기 처리
    * StringBuffer
        * 변경가능한 문자열
        * 동기 처리
        * multiple thread 환경에서 안전한 클래스(thread safe)

[#issue7] counting sort(계수정렬)의 개념 및 시간복잡도

* 원소 간 비교하지 않고 각 원소가 몇 번 등장하는지 개수를 세서 정렬하는 방법 
* 시간복잡도: O(n), 공간복잡도: O(n)

[#issue8] Java Collections Framework

Java-Collections-Framework

* Map
    * 검색할 수 있는 인터페이스
    * 데이터를 삽입할 때 Key와 Value의 형태로 삽입되며, Key를 이용해서 Value를 얻을 수 있다.
* Collection
    * List
        * 순서가 있는 Collection
        * 데이터를 중복해서 포함할 수 있다.
    * Set
        * 집합적인 개념의 Collection
        * 순서의 의미가 없다.
        * 데이터를 중복해서 포함할 수 없다.
* Collections Framework 선택 과정
  1. Map과 Collection 인터페이스 중 선택
    1-1. Collection 선택 시 사용 목적에 따라 List와 Set중 선택
  2. 사용 목적에 따라 Map, List, Set 각각의 하위 구현체를 선택
    2-1. Map: HashMap, LinkedHashMap, HashTable, TreeMap
    2-2. List: LinkedList, ArrayList
    2-3. Set: TreeSet, HashSet

[#issue8-1] java Map 인터페이스 구현체의 종류

* HashMap
    * Entry<K,V>의 배열로 저장되며, 배열의 index는 내부 해쉬 함수를 통해 계산된다.
    * 내부 hash값에 따라서 키순서가 정해지므로 특정 규칙없이 출력된다.
    * key와 value에 null값을 허용한다.
    * 비동기 처리
    * 시간복잡도: O(1)
* LinkedHashMap
    * HaspMap을 상속받으며, Linked List로 저장된다.
    * 입력 순서대로 출력된다.
    * 비동기 처리
    * 시간복잡도: O(n)
* TreeMap
    * 내부적으로 레드-블랙 트리(Red-Black tree)로 저장된다.
    * 키값이 기본적으로 오름차순 정렬되어 출력된다.
    * 키값에 대한 Compartor 구현으로 정렬 방법을 지정할 수 있다.
    * 시간복잡도: O(logn)
* ConCurrentHashMap
    * multiple lock
    * update할 때만 동기 처리 
    * key와 value에 null값을 허용하지 않는다.
* HashTable
    * single lock
    * 모든 메서드에 대해 동기 처리
    * key와 value에 null값을 허용하지 않는다.

[#issue8-2] java Set 인터페이스 구현체의 종류

* HashSet
    * 저장 순서를 유지하지 않는 데이터의 집합이다.
    * 해시 알고리즘(hash algorithm)을 사용하여 검색 속도가 매우 빠르다.
    * 내부적으로 HashMap 인스턴스를 이용하여 요소를 저장한다.
* LinkedHashSet
    * 저장 순서를 유지하는 HashSet
* TreeSet
    * 데이터가 정렬된 상태로 저장되는 이진 탐색 트리(binary search tree)의 형태로 요소를 저장한다.
    * 이진 탐색 트리 중에 성능을 향상시킨 레드-블랙 트리(Red-Black tree)로 구현되어 있다.
    * Compartor 구현으로 정렬 방법을 지정할 수 있다.

[#issue8-3] java List 인터페이스 구현체의 종류

* ArrayList
    * 단방향 포인터 구조로 각 데이터에 대한 인덱스를 가지고 있어 데이터 검색에 적합하다.
    * 데이터의 삽입, 삭제 시 해당 데이터 이후 모든 데이터가 복사되므로 삽입, 삭제가 빈번한 데이터에는 부적합하다.
* LinkedList
    * 양방향 포인터 구조로 데이터의 삽입, 삭제 시 해당 노드의 주소지만 바꾸면 되므로 삽입, 삭제가 빈번한 데이터에 적합하다.
    * 데이터의 검색 시 처음부터 노드를 순회하므로 검색에는 부적합하다.
    * 스택, 큐, 양방향 큐 등을 만들기 위한 용도로 쓰인다.
* Vector
    * 내부에서 자동으로 동기화 처리가 일어난다.
    * 성능이 좋지 않고 무거워 잘 쓰이지 않는다.

[#issue9] java 자료형의 범위 (ex. int, long, BigInteger, BigDecimal)

* int
    * 32bits
    * -$2^{31}$ ~ $2^{31}$-1 (-2,147,483,648 ~ 2,147,483,647)
    * 대략 20억
    * 10자리 수
    * 12! < int 범위 < 13!
* long
    * 64bits
    * -$2^{63}$ ~ $2^{63}$-1 (-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)
    * 대략 900경
    * 19자리 수
* BingInteger, BigDecimal
    * 크기 제한 없음(무한대)
    * 일반적인 operator 연산 불가
        * + : add()
        * - : subtract()
        * x : multiply()
        * / : divide()
        * % : mod()
        * == : compareTo()
    * BingInteger
        * 무한한 크기의 정수형 숫자
    * BigDecimal
        * 무한한 크기의 부동소수점 숫자

[#issue9-1] 입력값 조건에 따른 java 자료형 선택 방법

* 일반적으로 정수를 입력받을 때 int나 long을 사용
* 입력값의 조건을 보고 int나 long 중 선택
    * ex) 2 ≤ N ≤ 10000 : int
    * ex) 10억보다 작거나 같은 자연수 : int
    * ex) 19자리를 넘지 않는 자연수 : long
    * ex) 양의 정수이며 $2^{20}$보다 작다 : int
    * ex) 1 ≤ N ≤ 20, 1 ≤ k ≤ N! : long

[#issue10] 문자열 분리를 위한 StringTokenizer와 String.spilt의 차이

1. StringTokenizer
    * 개념
        * method가 아닌 java.util에 포함되어 있는 자체 class
        * 구분자(delemeter)로 나눈 문자열이 빈 문자열이면 빈 문자열은 포함하지 않고 출력한다.
2. String.split
    * 개념
        * String class의 method로, 추출한 문자를 배열로 저장
        * 구분자(delemeter)로 나눈 문자열이 빈 문자열이면 빈 문자열도 포함해서 출력한다. 
    * 사용법
        *  split의 구분자(delemeter)가 ^, *,| 등의 문자열일 경우 "\\"를 구분자 앞에 추가해주어야 한다.
3. 차이점
    1) 가장 큰 차이점은 구분자 사이에 데이터가 없는 경우, 즉 공백의 데이터가 포함된 경우
        * StringTokenizer: 공백의 문자열을 포함하지 않는다.
        * String.split: 공백의 문자열을 포함한다.
    2) 분해 방법
        * StringTokenizer: 문자열 하나 하나를 분해한다.
        * String.split: 내부적으로 정규 표현식으로 분해한다.
    3) 성능
        * StringTokenizer이 더 좋다.
        * 가급적 대용량 파일이나 데이터를 처리할 때에는 StringTokenizer는 쓰는 것이 더 좋다
        * 하지만 Sun에서는 StringTokenizer는 정규 표현식을 지원하지 않기 때문에 String.split를 권장한다.

[#issue10-1] 문자열 분리를 위한 StringTokenizer와 String.spilt의 사용 예제

  • StringTokenizer를 이용한 문자열 분리
String week = "월 화 수 목 금 토 일";
StringTokenizer st = new StringTokenizer(week, " ");

while( st.hasMoreTokens() ){
    System.out.println(st.nextToken());
}
  • String.split를 이용한 문자열 분리
String week = "월 화 수 목 금 토 일";
String[] array = str.split(" ");

for( String word : array ){
    System.out.println(word);
}

[#issue11] BufferedReader/Scanner, Arrays.sort()/Collections.sort()에 따른 시간복잡도 분석

* BufferedReader / Scanner (100만개 입력 결과)
    * BufferedReader: 0.452(sec)
    * Scanner: 2.441(sec)
    * Scanner가 BufferedReader보다 6배의 시간이 더 걸림
*  Arrays.sort() / Collections.sort() (100만개 정렬 결과)
    * Arrays.sort(): 0.009(sec)
    * Collections.sort(): ArrayList 자료형의 정렬일 때, 0.028(sec)
    * Collections.sort()가 Arrays.sort()보다 3배의 시간이 더 걸림
* 동일 문제에서의 걸린 시간 비교
    1) Scanner, Collections.sort() : 시간 초과
    2) Scanner, Arrays.sort() : 220312 KB / 5068 MS
    3) BufferedReader, Collections.sort() : 564748 KB / 4896 MS
    4) BufferedReader, Arrays.sort() : 478692 KB / 2072 MS

Reference

:house: Go Home