정렬이란?

정렬은, 배열이나 List에 담긴 값들을 원하는 기준으로 순서를 재배열하는 과정을 뜻한다.

정렬 알고리즘은 삽입, 선택, 힙, 퀵, 머지 등 하나하나 얘기하기 힘들정도로 다양하기 때문에 여기서 설명은 생략하려고 한다.

Stable vs Unstable

몇몇 정렬 문제에서 중요한 요소가 될 수 있는게 바로 이 부분이다.

간단하게 설명하자면 정렬에는 Stable한 정렬이 있고 반대로 Unstable한 정렬이 있다.

전자의 경우 비교값에 대하여, 값이 같을 경우, 즉 compareTo나 compare함수가 0을 반환하는 경우, 기존 배열의 순서가 유지된다.

하지만 후자의 경우 해당 순서가 유지된다는걸 보장하지 않는다.

위 그림을 보면 조금 쉽게 이해할 수 있다.

여기선 트럼프카드를 숫자에 대해서 오름차순으로 정렬하고 있는데, 위의 Stable한 정렬의 경우 같은 숫자인 5에 대하여 문양의 순서가 계속 유지되지만, 아래의 Unstable한 정렬의 경우 문양 순서가 뒤바뀔 수 있다.

Unstable한 소트의 대표격으론 Quick Sort가 있고, Stable한 소트에는 Merge Sort가 있다.

두 정렬은 비슷하지만 Quick Sort가 근소하게 더 빠르고, 별도의 공간이 필요하지 않기 때문에, 주로 stable해야하는 소트엔 Merge가 그렇지 않은 경우 Quick을 사용한다.

🚀주요 사용하는 기능 in JAVA

Arrays.sort

T[] arr = new T[N];
Arrays.sort(arr);

[]로 표시되는 단순 배열을 정렬하는 메서드.

이 때 타입 T는 반드시 Comparable 인터페이스를 구현한 상태여야 한다. 참고로 Unstable한 Quick Sort를 사용한다고 한다.

Collections.sort

ArrayList<T> arr = new ArrayList<>();
Collections.sort(arr);
Collections.sort(arr, new Comparator());

위의 소트와 사용방법은 거의 비슷하다.

참고할 점은 추가인자로 Comparator를 삽입하여 정렬 순서를 정의할 수 있다는 점, 그리고 MergeSort를 사용하기 때문에 Stable하다는 것 정도이다.

---

K번째수 (Level 2)

정렬파트의 몸풀기 문제.

할 말이 딱히 없다ㅠ 그냥 정렬만 할 수 있으면 푸는 문제

import java.util.*;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];
        int k = 0;
        for(int[] command : commands){    
            ArrayList<Integer> arr = new ArrayList<>();
            for(int i = command[0]-1 ; i < command[1] ; i++){
                arr.add(array[i]);
            }
            Collections.sort(arr);
            answer[k++] = arr.get(command[2]-1);
        }
        return answer;
    }
}

가장 큰 수 (Level 2) ⭐️⭐️⭐️

이번 프로그래머스 문제를 풀기 시작한 이래 가장 큰 걸림돌이 됐던 문제.

사실 아이디어 한 줄이면 풀 수 있는 문제인데, 그걸 떠오르는게 힘들었다.

모든 정렬 문제를 관통하며, 이 문제에서도 가장 핵심적인 아이디어는 다음과 같다..

어떤 List에서 임의의 두 요소에 대한 순서규칙만 정의한다면, 정렬 알고리즘(함수)를 통해 List 전체를 정렬할 수 있다.

기본적으로 정렬함수는 오름차순으로 정렬하지만, 우리는 Comparator와 Comparable을 통해 임의의 기준을 부여할 수 있다는 걸 알 수 있다.

즉, 두 요소에 대해 적절한 규칙만 정의해준다면, 전체를 정렬하는건 단순한 함수 한줄이면 가능하다.

자 이제 두 요소를 비교할 기준만 만들면 된다.

단어 A랑 단어 B를 붙여서 새로운 단어를 만든다고 했을 때 AB와 BA중 어느게 앞에올까?

사실 고민할 필요도 없다. 그냥 두 단어를 일단 붙여보고 비교하면 된다.

위 방법들에 대한 내용을 코드로 바꾼게 바로 아래내용이다.

import java.util.Arrays;
import java.util.Comparator;

class Solution {
	public String solution(int[] numbers) {
		String[] strNum = new String[numbers.length];
		boolean flag = false;
        for (int i = 0; i < numbers.length; i++) {
			strNum[i] = numbers[i] + "";
            if(numbers[i] != 0)
                flag = true;
		}
        if(!flag){
            return "0";
        }
		Arrays.sort(strNum, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				String s1 = o1+o2;
                String s2 = o2+o1;
				return Integer.parseInt(s2) - Integer.parseInt(s1);

			}
		});
		String answer = "";
		for(int i=0 ; i<numbers.length ; i++) {
			answer += strNum[i];
		}
		
		return answer;
	}
}

H-Index (Level 2)

먼저 정렬을 해야겠다는 생각까지 하긴 쉽다.

그 다음이 중요한데, 내림차순으로 내려가면서, 최대 논문 편수를 기준으로 최대 H-index가 몇인지 한단계씩 비교해가며 내려가면 된다.

import java.util.Arrays;

class Solution {
    public int solution(int[] citations) {
        int len = citations.length;
        Arrays.sort(citations);
        int answer = citations[len-1];
        for(int i= 1 ; i<=len ; i++) {
            int idx = len-i;
            while(answer > citations[idx]){
                if(answer <= i-1){  
                    return answer;
                }
                answer--;
            }
            if(answer <= i) {
                return answer;
            }
        }
        while(answer > len){
            answer--;
        }
        return answer;
    }
}