[묘공단] 코딩 테스트 합격자 되기 - 정렬

코딩 테스트 합격자 되기 자바편

 

책 제목 : 코딩 테스트 합격자 되기 자바편

지은이 : 김희성

 

0. 정의

 

정렬이란 사용자가 정의한 순서로 데이터를 나열하는 것을 말한다.

사용자가 정의한 순서는 오름차순이나 내림차순일수도 있고 임의의 조건이 될 수 도 있다.

 

1. 삽입정렬

정렬이되지않은 영역과 정렬된 영역을 나눠서 정렬을 진행한다.

 

아래 그림과 같이 하나씩 좌측으로 옮기면서 자신의 좌측이 작을때까지 하나씩 이동한다.

 

 

2. 병합정렬

분할하고 정복한다는 방식을 취한다.

데이터를 부분적으로 나눈 후에 각 나눠진 내부에서도 하나씩원소를 쪼갠다.

그 후에 자체적으로 정렬을 수행하며 병합한다.

그리고 마지막에 처음 부분적으로 나눈 값을 병합하여 하나의 배열로 만든다.

 

3. 힙정렬

여기에서의 힙은 특정 규칙이 있는 이진트리를 의미한다.

최대 힙 구조는 부모 노드가 자식 노드보다 크고, 최소힙은 부모 노드가 자식 노드보다 작다.

 

최소힙의 반대가 최대힙이라고 생각하면되고 다음 그림과 같이 동작한다.

 

 

예시 문제

문제 설명

문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. 

 

제한 조건 

strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. 

strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 큽니다. 인덱스 1의 문자가 같은 문자열이 여럿 일 경우, 사전순으로 앞선 문자열이 앞쪽에 위치합니다.

 

입출력 예)

 

strings

["sun", "bed", "car"]

 

n

1

 

return ["car", "bed", "sun"]

import java.util.stream.Stream;
import java.util.Comparator;

class Solution {
    public String[] solution(String[] strings, int n) {
        String[] answer = {};

        answer = Stream.of(strings)
            .sorted(Comparator.comparing(text -> text.toString().charAt(n))
            .thenComparing(text -> text.toString())).toArray(String[]::new);
        return answer;
    }
}