[임시] 정렬

보통 정렬 쓸 땐 퀵 정렬이나 병합 정렬을 많이 코테에서 쓴다고 함

버블 정렬

 

• 버블 정렬: 데이터 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식
  • 한 번 반복할 때마다 가장 큰 요소가 제일 뒤에 가게 됨(오름차순 기준)  => 그럼 제일 뒤의 요소들은 정렬되어 건드릴 필요가 없는 영역임.
  • 간단하게 구현 가능하지만, 시간 복잡도가 n의 제곱으로 다른 정렬 알고리즘보다 속도 느림
  • 구현 원리는 영상과 교재 보기

문제 15, 수 정렬하기, 2750번

 

이 문제 그냥 sort로 해결 가능

굳이 버블 정렬로 구현하면 이중 for문으로 가능

 

for (int i = 0; i < N - 1; i++) {
      for (int j = 0; j < N - 1 - i; j++) {
        if (A[j] > A[j + 1]) {
          int temp = A[j];
          A[j] = A[j + 1];
          A[j + 1] = temp;
        }
      }
    }

=> 왜 i < N - 1 대신 i < N가 아닌가요?

버블 정렬에서는 배열을 완전히 정렬하기 위해 여러 번 반복합니다. i < N - 1가 사용되는 이유는 다음과 같습니다:

1. N-1 회전: 외부 반복문의 목적은 배열의 정렬되지 않은 부분의 가장 큰 요소가 올바른 위치로 이동하도록 여러 번 통과하는 것입니다. 따라서 배열을 완전히 정렬하려면 N-1 회전이 필요합니다.
   • 예를 들어, N = 5라면 4번의 회전이 필요합니다(0에서 3까지). 왜냐하면 4번의 회전 후에는 가장 큰 4개의 요소가 제자리에 있게 되고, 따라서 5번째 요소는 자연스럽게 제자리에 있게 됩니다.
2. 불필요한 회전: 만약 i < N을 사용하면, 배열이 이미 정렬된 후에도 불필요한 한 번의 추가 회전이 발생합니다.

 

문제 16, 버블 소트, 1377번

• changed가 false로 남아 있으면, 이는 배열이 이미 정렬되었음을 의미합니다. 이 경우 반복을 중단하고 현재 반복 횟수를 출력합니다.
  
  • 버블 정렬 swap이 한 번도 일어나지 않은 루프(바깥 for문과 관련)가 언제인지 알아내는 문제
  • 안쪽 for문 전체를 돌 때 swap이 일어나지 않았다는 것은 이미 모든 데이터가 정렬됐다는 것을 의미

 

• n의 최대 범위가 50만이라 버블 정렬로 풀면 시간을초과할 수 있음. 안쪽 for문이 몇 번 수행됐는지 구하는 다른 아이디어 필요
  • 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 됨
  • 안쪽 루프는 1에서 n-i까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻 

=> 이 부분을 이해해보면

즉, 오른쪽으로 이동하는 것과 대조하면 이해하기 쉬움
첫 번째 요소로 10이 들어가 있으면, 예제 1에서는 10이 최대 4번 이동함. 안쪽 루프 한 번 돌때

그러나 반대로 왼쪽으로 이동한다는 뜻은, 안쪽 루프가 한 번 돌때 딱 한번만 자리를 왼쪽으로 옮길 수 있음.
버블 정렬 과정을 떠올리면 됨

즉 이렇게 왼쪽으로 이동하는 것을 안쪽 루프 한 번 돌았다로 치환하는 거지.

그리고 왼쪽으로 제일 많이 이동한 것을 찾는다는 소리는, 
봐봐, 오름차순으로 정렬이 완성되기 전까진 계속 스왑하면서 자리를 옮길 거임
그렇게 옮긴 횟수만큼 바깥쪽 for문이 계속 돌았다는 걸 의미

제일 많이 왼쪽으로 움직인 것의 횟수는 곧 안쪽 for문이 정렬 완료될 때까지 몇 번 수행되었는지를 알 수 있음

 

• 각 데이터마다 정렬 전 index 값에서 정렬 후 index 값을 배고 최댓값을 찾음. 그리고 swap이 일어나지 않는 반복문이 한 번 더 실행되는 것을 감안해 최댓값에 1을 더함?
  • +1을 하는 이유는 정렬 후에 i++ 한 값이 출력되기 때문이다.

=> 즉 정렬 전 index 값에서 정렬 후 index 값을 뺀 값은 안쪽 for문이 몇 번 돌았는지이다. 

하지만 출력은 바깥 for문의 i다.

그러니 예제 1을 예시로 들면, 3이 최대 2번 왼쪽으로 이동했다,.

3이 2번 이동한 후 정렬이 완료된 상태.

 

하지만 어쨌거나 3이 이 때 한 번 왼쪽으로 이동한 셈이니까, change 변수는 true가 됨

그러니 다시 바깥 for문이 한 번 더 도는 거지

그 후 더 이상 안쪽 for문으로 스왑할 게 없으니까,

change 변수는 false로 유지되고, 조건문을 타서 현재 i값을 출력하는 셈이 됨

 

•  mData[] A = new mData[N];
      for (int i = 0; i < N; i++) {
        A[i] = new mData(Integer.parseInt(reader.readLine()), i);
      }
• class mData implements Comparable<mData> {
    int value;
    int index;
  
    public mData(int value, int index) {
      super();
      this.value = value;
      this.index = index;
    }
  
    @Override
    public int compareTo(mData o) {//value 기준 오름차순 정렬
      return this.value - o.value;
    }
  }

=> 거시적으로 짚고 넘어갈 부분

• 인터페이스와 클래스?
  • 인터페이스는 메소드를 선언한 할 뿐, 그 내용은 구체화하지 않은 클래스이다.
  • 여기서 각 메소드를 구체적으로 구현한 것이 클래스다
• Comparable? 인터페이스와 오버라이드?
  • 인터페이스다. 즉 이를 이용하려면 인터페이스에서 선언된 메소드를 반드시 구현해야 한다
  • 이 인터페이스에선 compareTo() 하나가 선언되어 있다. 따라서 Comparable를 사용하려면 compareTo() 메소드를 재정의, 즉 오버라이딩 해야 한다.
• Comparable 쓰는 이유?
  • 객체를 비교할 때 쓰임
  • 기본 자료형, 즉 정수형이나 실수형 등의 비교는 부등호로 가능
  • 그러나 사용자가 새로 정의한 클래스의 책체끼리 대소관계 비교할 땐 부등호로 못함
  • 왜? mData라는 클래스에선 value와 index 두 개가 있는데, 이 둘 중 어떤 걸 우선시 해서 비교할 지 정하지 않으면 비교 불가임
• compareTo()? Comparator의 compare()와의 차이점?
  • compareTo()는 자기자신과 매개변수로 받은 객체를 비교함
    • 이 때 자기자신은 정답 코드에선 this.value고 매개변수 객체는 o.value이다.
    • 뭐 compareTo가 음수를 반환할 때와 양수를 반환할 때의 차이는 일반적인 정렬 알고리즘과 비슷하지 않을까?
    • 즉 오름차순이 디폴트니까 앞에 요소가 커서 first-second 값이 양수가 나오면 서로 자리 스왑하고, 음수나 0이면 그대로 유지하지 않을까? => 나중에 한 번 코드 간단히 출력과 실행해보면 알 수 있을듯. 챗 지피티도 있고
    • 보니까 정답 코드 주석에 "//value 기준 오름차순 정렬" 되어있네. 그럼 양수일 때 스왑, 음수일 때 유지가 맞겠다
  • Comparator의 compare()와의 차이점?
    • compare는 두 매개변수를 받고, 두 매개변수를 비교하는 거고
    • compareTo는 자기자신과 매개변수 하나를 비교하는 것에서 차이가 남

 

Comparator와 Comparable의 차이와 사용법

1. Comparator와 Comparable의 사용 시기 및 차이

• Comparable 인터페이스는 객체의 자연 정렬 순서를 정의하기 위해 사용됩니다. 객체 자체에 정렬 로직을 포함시켜 한 가지 기준으로 정렬할 때 사용합니다.
• Comparator 인터페이스는 두 개의 객체를 비교하기 위한 외부 비교자를 정의할 때 사용됩니다. 여러 기준으로 정렬하거나, 기존 클래스에 정렬 로직을 추가하고 싶을 때 사용합니다.

주요 차이점:

• Comparable:
  • 인터페이스: java.lang.Comparable<T>
  • 메서드: compareTo(T o)
  • 목적: 객체 자체에 정렬 기준을 정의
  • 사용 예: 기본적으로 정렬 가능한 객체 (예: String, Integer)
• Comparator:
  • 인터페이스: java.util.Comparator<T>
  • 메서드: compare(T o1, T o2)
  • 목적: 객체 외부에 여러 정렬 기준을 정의
  • 사용 예: 특정 상황에서 다른 기준으로 정렬해야 하는 경우 (예: 사용자 정의 객체, 다양한 정렬 조건)

2. 각 인터페이스의 뉘앙스 차이

• Comparable:
  • 주체적인 비교: 객체 자신이 다른 객체와 비교할 수 있는 능력을 가짐.
  • 내부 구현: 정렬 기준이 객체 내부에 포함됨. compareTo 메서드를 구현하여 정렬 기준을 명시.
  • 일관성: 클래스가 하나의 자연스러운 정렬 순서를 가지고 있는 경우 유용. 예를 들어, String 클래스는 알파벳 순으로 정렬.
  • public class Person implements Comparable<Person> {
        private String name;
        private int age;
    
        public Person(String name, int age) {
            this.name = name;
            this.age = age;
        }
    
        @Override
        public int compareTo(Person other) {
            return this.age - other.age; // 나이 순으로 정렬
        }
    
        // Getters and toString() methods
    }
• Comparator:
  • 객체 외부의 비교자: 비교 로직이 객체 외부에 존재. 다양한 기준으로 정렬 가능.
  • 유연성: 같은 객체를 여러 기준으로 정렬할 수 있음. 필요에 따라 다양한 비교자를 정의 가능.
  • 구현의 독립성: 클래스 정의를 변경하지 않고도 다양한 정렬 기준을 제공.
  • import java.util.Comparator;
    
    public class PersonNameComparator implements Comparator<Person> {
        @Override
        public int compare(Person p1, Person p2) {
            return p1.getName().compareTo(p2.getName()); // 이름 순으로 정렬
        }
    }
    
    // 다른 Comparator
    public class PersonAgeComparator implements Comparator<Person> {
        @Override
        public int compare(Person p1, Person p2) {
            return p1.getAge() - p2.getAge(); // 나이 순으로 정렬
        }
    }
• 사용 예시
• import java.util.ArrayList;
  import java.util.Collections;
  import java.util.List;
  
  public class Main {
      public static void main(String[] args) {
          List<Person> people = new ArrayList<>();
          people.add(new Person("Alice", 30));
          people.add(new Person("Bob", 25));
          people.add(new Person("Charlie", 35));
  
          // Comparable을 사용한 정렬
          Collections.sort(people);
          System.out.println("나이 순 정렬: " + people);
  
          // Comparator를 사용한 정렬
          Collections.sort(people, new PersonNameComparator());
          System.out.println("이름 순 정렬: " + people);
      }
  }
• 정리
  • Comparable은 클래스 내부에 하나의 자연스러운 정렬 순서를 정의할 때 사용합니다.
  • Comparator는 클래스 외부에서 다양한 정렬 기준을 정의할 때 사용합니다.
  • 두 인터페이스 모두 객체 비교를 위한 것이지만, Comparable은 기본 정렬을 위해, Comparator는 사용자 정의 정렬을 위해 사용됩니다.

 

=> 미시적으로 짚을 부분

• implements Comparable<mData>
  • 인터페이스 상속할 때 implments를 씀
• super()? 없지 않아도 되지 않아?
  • 부모 클래스의 생성자를  호출하는 것을 의미.
  • super() 메소드예제 코드 분석
    • 주어진 코드에서 mData 클래스는 다른 클래스를 상속받지 않기 때문에 super()는 부모 클래스인 Object의 기본 생성자를 호출합니다. 부모 클래스 Object의 기본 생성자는 특별히 초기화할 내용이 없기 때문에 super()를 명시적으로 호출할 필요는 없습니다.
    • super()는 자바에서 부모 클래스의 생성자를 호출하는 데 사용됩니다. 만약 클래스가 다른 클래스에서 상속받은 것이 아니라면, super()는 부모 클래스 Object의 기본 생성자를 호출합니다. 부모 클래스의 생성자가 특별히 초기화해야 할 것이 없으면 super()를 명시적으로 호출할 필요는 없습니다. 자바 컴파일러는 기본적으로 super()를 자동으로 삽입합니다.

---

선택 정렬

코테에서 별로 나오지 않음. 시간 복잡도도 n의 제곱으로 안 쓰이고 구현도 복잡하고

저자 말로 가끔 다른 문제에 끼여 오거나, 기술 면접에서 물어볼 수 있다고 하는데,

난 코테를 합격하려고 하지, 컴과는 다른 책으로 공부할 거기에 대충 넘어가면 됨

 

선택 정렬 자체를 몯는 문제는 잘 없고, 이 원리 으용하는 문제는 나올 수 있으니

선택 정렬 원리만 간단히 알아두면 됨

대충 원리는 최솟값 또는 최댓값 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap해라인데, 

자세한 건 강의와 교재 참고하기

 

17번, 소트인사이드

• 숫자를 각 자릿수별로 나누는 작업
  • 나머지 연산을 분리도 가능
  • 입력값을 String으로 받은 후 subString() 함수로 자릿수 단위로 분리하고, 이를 다시 int형으로 변경해 배열에 저장해도 됨
• str.length(); 스트링 변수 뒤에 length()란 메소드가 있구나
• A[i] = Integer.parseInt(str.substring(i, i + 1));
  • String subString(int beginIndex, int endIndex): bi 위치의 값부터, ei 앞의 값까지의 값을 리턴

---

삽입 정렬

시간복잡도 n의 제곱이기에 코테에선 잘 사용 안 함

이것도 선택정렬처럼 면접에서나 물어보니 작동 원리를 알아라고 함

대충 현재 선택한 데이터가 정렬된 범위에 삽입될 위치를 탐색 후, 들어갈 자리가 정해지면

기존에 있던 애들 싹 다 오른쪽으로 시프트하고 그 자리 내 차지란 느낌

 

문제 18, ATM

각 사람이 인풀에 필요한 시간은, 앞사람들의 인출 시간의 합 + 자신의 인출 시간이므로

합 배열로 풀면 됨

 

교재 해설은 삽입 정렬 구현해서 풀었지만, 

그냥 Array.sort() 사용해서 오름차순 정렬 후 합 배열 이용하면 풀리지 않나?

한 번 테스트 나중에 해봐야 겠다.

 

---

퀵 정렬

시간 복잡도가 평균적으로 nlogn이므로(운이 진짜 나쁘면 n의 제곱이지만) 코테에서 종종 응용함

재귀 함수의 형태로 직접 구현할 수 있음, 물론 쉽진 않음

 

대략 원리 핵심은 기준이 되는 값(pivot)을 아무렇게나 기준 설정해

그리고 오름차순으로 정렬한다면,

배열에서 pivot보다 왼쪽에 있는 건 전부 작은 걸로만 채우고, 

오른쪽은 무조건 전부 큰 것만 있게 만들고 싶은 거지

 

그리고 왼쪽 부분, 오른쪽 부분 각각에 이 짓을 계속 반복하는 거지(재귀적임)

그렇게 해서 왼쪽 부분, 오른쪽 부분에서 원소 개수가 하나일 땐 더 이상 할 필요가 없고

 

문제 19번, k번째 수 구하기

(안 푼 상태에서의 내 망상) 그냥 array.sort하고 k번째 인덱스 값 바로 print하면 끝아님? 

=> 보니까 이 책에 나온 문제 웬만하면 arrays.sort 함수로 풀림. 실버 문제들은. 

 

• pivot을 어떤 값으로 정해서 k번째 수를 더 빨리 구할 수 있을까? 배열의 중간 위치를 pivot으로 설정하면 됨

정답코드에서 swap (A, i++, j--) 부분

=> 애초에 swap에서 i++, j++한 이유는 그래야 while 문 반복이 끝나네

=> 그리고 이렇게 적은 이유는 그냥 간결하게 한 줄로 적은 거고.

 

partition 함수는 퀵 정렬(Quick Sort) 알고리즘의 핵심 부분으로, 배열을 피벗(Pivot)을 기준으로 두 부분으로 나눕니다. 이 함수는 주어진 배열의 부분 배열에서 피벗보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킵니다.

 

 

 

Base Case 처리

if (S + 1 == E) {
    if (A[S] > A[E]) swap(A, S, E);
    return E;
}

• 배열의 구간 길이가 2인 경우, 단순히 두 요소를 비교하여 순서를 바꾼 후, 종료합니다.
• 이 부분은 작은 배열 구간에서의 최적화를 위해 사용됩니다.

피벗 선택 및 이동

int M = (S + E) / 2;
swap(A, S, M);
int pivot = A[S];

• 중간값을 피벗으로 선택하여 첫 번째 요소와 교환합니다. 이는 피벗 선택의 전략 중 하나로, 중앙값을 선택하여 평균적으로 좋은 분할을 기대합니다.
• 피벗 값을 저장합니다.

 

두 포인터 초기화

int i = S + 1, j = E;

• i는 피벗 다음 위치, j는 마지막 위치에서 시작합니다.

파티셔닝 루프

while (i <= j) {
    while (pivot < A[j] && j > 0) j--;
    while (pivot > A[i] && i < A.length - 1) i++;
    if (i <= j) {
        swap(A, i++, j--);
    }
}

• i와 j가 만나거나 교차할 때까지 반복합니다.
• 왼쪽 포인터 i는 피벗보다 큰 값을 찾을 때까지 증가합니다.
• 오른쪽 포인터 j는 피벗보다 작은 값을 찾을 때까지 감소합니다.
• i가 j보다 작거나 같으면, 두 값을 교환한 후 포인터를 각각 이동시킵니다.

피벗 위치 조정

A[S] = A[j];
A[j] = pivot;

• 피벗을 최종 위치에 놓습니다. 최종 위치는 j입니다.
• 이로 인해 피벗을 기준으로 왼쪽에는 피벗보다 작은 값들이, 오른쪽에는 큰 값들이 위치하게 됩니다.

 

왜 quickSort 함수에서 S에 0, E에 N-1, K에 K-1을 넣는가?

1. 인덱스의 의미:
   • S와 E는 배열의 시작과 끝 인덱스를 나타냅니다.
     • S = 0은 배열의 첫 번째 요소를 의미합니다.
     • E = N-1은 배열의 마지막 요소를 의미합니다.
   • K는 찾고자 하는 K번째 수의 인덱스를 의미합니다. 하지만 배열의 인덱스는 0부터 시작하므로, K-1을 넣어 실제로 찾고자 하는 위치를 맞춰줍니다.
2. 0 기반 인덱스:
   • Java 배열의 인덱스는 0부터 시작합니다. 예를 들어, 배열의 첫 번째 요소는 인덱스 0에 있습니다.
   • 만약 K번째 수를 찾고자 한다면, 이는 인덱스 K-1에 해당합니다. 예를 들어, 3번째 수를 찾고자 한다면 배열의 인덱스 2에 위치한 값을 찾아야 합니다.

왜 출력은 K번째 수가 아니라 K-1번째를 출력하는가?

1. 1 기반 vs 0 기반 인덱스:
   • 일반적으로 문제에서 "K번째 수"라고 하면 이는 1 기반 인덱스를 의미합니다. 즉, 배열에서 첫 번째 요소가 1번째 수가 됩니다.
   • 하지만 배열의 인덱스는 0부터 시작하므로, K번째 수는 배열의 K-1번째 인덱스에 위치하게 됩니다.
   • 예를 들어, 5개의 요소가 있는 배열에서 3번째 수를 찾는다고 하면, 이는 배열의 인덱스 2에 해당합니다. 배열의 인덱스는 0, 1, 2, 3, 4로 되어 있습니다.

코드 설명

• quickSort(A, 0, N - 1, K - 1);:
  • 배열 A를 0번째 인덱스부터 N-1번째 인덱스까지 정렬합니다.
  • K-1을 전달하여 실제로 K번째 수가 배열의 K-1 인덱스에 위치하도록 합니다.
• System.out.println(A[K - 1]);:
  • 정렬이 완료된 후 배열의 K-1번째 요소를 출력합니다. 이는 문제에서 요구한 K번째 수가 됩니다.

이렇게 함으로써 문제에서 요구한 K번째 수를 정확하게 찾아 출력할 수 있습니다.

 

---

병합 정렬

병합 정렬의 이론과 원리가 다른 정렬 알고리즘과 다르게, 

코테에서 이해하고 응용해서 푸는 문제가 종종 많이 나오기 때문

=> 코테 정렬 관련 문제에서 자주 등장하며, 이 원리와 아이디어 가지고 풀 수 있는 문제 많이 나옴

=> 특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야 함 

=> 응용하는 포인트는 강의 영상 막바지에 있으니 확인하고

 

문제 20, 수 정렬하기2

한쪽 그룹이 모두 선택된 후 남아있는 값 정리하기

while (index1 <= m) {
    A[k] = tmp[index1];
    k++;
    index1++;
}
while (index2 <= e) {
    A[k] = tmp[index2];
    k++;
    index2++;
}

• 이 부분은 두 그룹 중 하나가 먼저 병합을 완료한 후 나머지 요소들을 병합된 배열에 추가하는 과정입니다.
• 병합 과정에서 두 포인터 중 하나는 먼저 끝에 도달할 수 있습니다. 예를 들어, 첫 번째 부분 배열의 모든 요소가 병합되었지만, 두 번째 부분 배열에는 여전히 요소가 남아 있을 수 있습니다.
• 첫 번째 while 루프는 첫 번째 부분 배열의 남아 있는 요소들을 병합된 배열에 추가합니다.
• 두 번째 while 루프는 두 번째 부분 배열의 남아 있는 요소들을 병합된 배열에 추가합니다.

 

문제 21, 버블 소트 프로그램2

두 그룹을 병합하는 과정에서 예로 5번째 칸에 있는 두번 째 그룹 숫자 5가

오름차순으로 정렬할 때 결과 배열에 첫 번째로 가게 되면

4칸만큼 앞으로 이동, 즉 4번 swap한 것과 동일함

=> 병합 정렬 구현을 20번과 동일하게 하되, 정렬 과정에서 index가 이동한 거리를 변수에 저장하면 됨

---

기수 정렬

 

주류일 알고리즘 정렬이 아님

문제가 어렵게 나올 경우 사용해야 할 경우 있음

이런 게 있고 이런 원리로 움직인다고만 알아두면 좋을 것 같다

 

자릿수만 비교

시간 복잡도는 kn이고, 여기서 k는 자릿수를 뜻함

즉 데이터 개수 n이 백만이고, 데이터 수의 범위가 10000까지라고 하면

엄밀히 따지면 자릿수 개수는 5개지만, 10000보다 작다고 하면 9999니까 4이다.

그리고 이 4가 k를 뜻함

⇒ 즉 데이터 개수가 굉장히 많지만, 각 데이터의 수의 자릿수가 짧을 때는 기수 정렬 사용하는 것도 좋은 방법 중 하나다

⇒ 정렬할 데이터 수가 너무 많으면 기수 정렬 알고리즘을 사용해도 되지만

⇒ 기수 정렬을 사용한 약간 어려워 지는데, 이론만 들으면 쉽지만, 이를 코드로 구현하는 건 약간 어렵다고 함

⇒ 그러니 한 번 구현해 보면 좋다고 함

 

기수 정렬은 10개의 큐를 사용함

⇒ 즉 한 자릿수에 올 수 있는 게 0~9아닌가. 그러니 10개를 사용함

작은 자릿수부터, 즉 일의 자릿수부터 기준으로 잡고 정렬하는 이유는

⇒ 일의 자릿수 기준으로 정렬하고 그 다음 십의 자릿수 기준으로 정렬하는 이유는

⇒ 십의 자리가 똑같을 때 일의 자리 수가 작은 애가 먼저 들어가게끔 해주기 때문

⇒ 큐의 FIFO와도 연관 있음

 

22번, 수 정렬하기3

n의 최대 개수가 천만으로 매우 크기에 nlogn보다 더 빠른 알고리즘이 필요함

=>  log⁡10,000,000≈ log(10^7)≈7×log⁡10≈7×3.32193≈23.25351

=> 따라서 nlogn은 10,000,000×23.25351≈232,535,100=> 2억이라 2초 이상이 거리는데...=> 근데 이 문제 제한 시간이 3초인데...? 그냥 nlogn 사용해도 되는 거 아니야?

 

자릿수가 서로 다른 경우 자릿수가 적은 수 앞에 0이 채워져 있다고 생각하여 큐에 삽입해야 함

 

일반적 기수 정렬은 우선순위 큐를 사용해 비교적 간단하게 구하는 방법 있음그러나 복잡도를 느리게 하는 요소 있음=> 따라서 구간 합을 이용하는 방법으로 구현함=> bucket 배열의 정확한 의미와 bucket 배열로 현재 자리를 기준으로 정렬하는 법 이해하고 넘어가라

 

---

입력값

11 215 15 344 372 294 100 8 145 24 198 831

bucket 배열 초기화 및 채우기
각 숫자의 일의 자리수를 기준으로 빈도를 계산:

A = [215, 15, 344, 372, 294, 100, 8, 145, 24, 198, 831]

bucket = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

bucket[5]++, bucket[5]++, bucket[4]++, bucket[2]++, bucket[4]++, bucket[0]++, bucket[8]++, bucket[5]++, bucket[4]++, bucket[8]++, bucket[1]++

 

bucket = [1, 1, 1, 0, 3, 3, 0, 0, 2, 0]
누적합 배열로 변환:
for (int i = 1; i < 10; i++) { bucket[i] += bucket[i - 1]; } bucket[1] += bucket[0] -> bucket[1] = 2 bucket[2] += bucket[1] -> bucket[2] = 3 bucket[3] += bucket[2] -> bucket[3] = 3 bucket[4] += bucket[3] -> bucket[4] = 6 bucket[5] += bucket[4] -> bucket[5] = 9 bucket[6] += bucket[5] -> bucket[6] = 9 bucket[7] += bucket[6] -> bucket[7] = 9 bucket[8] += bucket[7] -> bucket[8] = 11 bucket[9] += bucket[8] -> bucket[9] = 11 

bucket = [1, 2, 3, 3, 6, 9, 9, 9, 11, 11]

정렬 및 배열 업데이트
배열을 역순으로 순회하면서 output 배열을 채우고 bucket 배열을 업데이트합니다.

i = 10:
A[10] = 831 bucket[1] = 2 -> output[1] = 831 -> bucket[1]-- 

output = [0, 831, 0, 0, 0, 0, 0, 0, 0, 0, 0] bucket = [1, 1, 3, 3, 6, 9, 9, 9, 11, 11]

i = 9:
A[9] = 198 bucket[8] = 11 -> output[10] = 198 -> bucket[8]-- 

output = [0, 831, 0, 0, 0, 0, 0, 0, 0, 0, 198] bucket = [1, 1, 3, 3, 6, 9, 9, 9, 10, 11]

i = 8:
A[8] = 24 bucket[4] = 6 -> output[5] = 24 -> bucket[4]-- 

output = [0, 831, 0, 0, 0, 24, 0, 0, 0, 0, 198] bucket = [1, 1, 3, 3, 5, 9, 9, 9, 10, 11]

i = 7:
A[7] = 145 bucket[5] = 9 -> output[8] = 145 -> bucket[5]-- 

output = [0, 831, 0, 0, 0, 24, 0, 0, 145, 0, 198] bucket = [1, 1, 3, 3, 5, 8, 9, 9, 10, 11]

i = 6:
A[6] = 8 bucket[8] = 10 -> output[9] = 8 -> bucket[8]-- 

output = [0, 831, 0, 0, 0, 24, 0, 0, 145, 8, 198] bucket = [1, 1, 3, 3, 5, 8, 9, 9, 9, 11]

i = 5:
A[5] = 100 bucket[0] = 1 -> output[0] = 100 -> bucket[0]-- 

output = [100, 831, 0, 0, 0, 24, 0, 0, 145, 8, 198] bucket = [0, 1, 3, 3, 5, 8, 9, 9, 9, 11]

i = 4:
A[4] = 294 bucket[4] = 5 -> output[4] = 294 -> bucket[4]--

 output = [100, 831, 0, 0, 294, 24, 0, 0, 145, 8, 198] bucket = [0, 1, 3, 3, 4, 8, 9, 9, 9, 11]

i = 3:
A[3] = 372 bucket[2] = 3 -> output[2] = 372 -> bucket[2]-- 

output = [100, 831, 372, 0, 294, 24, 0, 0, 145, 8, 198] bucket = [0, 1, 2, 3, 4, 8, 9, 9, 9, 11]

i = 2:
A[2] = 344 bucket[4] = 4 -> output[3] = 344 -> bucket[4]-- 

output = [100, 831, 372, 344, 294, 24, 0, 0, 145, 8, 198] bucket = [0, 1, 2, 3, 3, 8, 9, 9, 9, 11]

i = 1:
A[1] = 15 bucket[5] = 8 -> output[7] = 15 -> bucket[5]--

 output = [100, 831, 372, 344, 294, 24, 0, 15, 145, 8, 198] bucket = [0, 1, 2, 3, 3, 7, 9, 9, 9, 11]

i = 0:
A[0] = 215 bucket[5] = 7 -> output[6] = 215 -> bucket[5]-- 

output = [100, 831, 372, 344, 294, 24, 215, 15, 145, 8, 198] bucket = [0, 1, 2, 3, 3, 6, 9, 9, 9, 11]

---

위 내용은 챗 지피티에게서 뽑은 내용이다

내가 이해 안 된 점이 해소되었다

 

      for (int i = A.length - 1; i >= 0; i--) { // 현재 자리수 기준으로 정렬하기
        output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];
        bucket[(A[i] / jarisu) % 10]--;
      }

=> 이 부분 이해 안 되었지만, 지금은 이해했다

•  bucket[(A[i] / jarisu) % 10]--;의 역할은 뭐냐?
  • 그러니까 입력값 중에서 24, 294, 344 세 가지는 일의 자리를 기준으로 했을 때 다 4이다
  • 만약 이 코드 한 줄이 없었다고 치자. 그럼 output[bucket[(A[i] / jarisu % 10)] - 1] = A[i]; 부분에서 문제가 생김
  • bucket = [1, 2, 3, 3, 6, 9, 9, 9, 11, 11]로 --되지 않고 유지된다면, 
  • a[i]가 24든 294든 344든 결국 전부 output[bucket[4]-1]이 된다. 즉  output[6-1=5]에 24, 294, 344를 저장하는 셈이다
  • 하지만 이렇게 되면 문제가 보인다. 처음에 24를 output[5]에 저장했는데, 나중에 다시 294를 똑같이 저장하면 덮어씌워지고 정렬이 제대로 안 됨
• 위 내용을 보면 bucket을 왜 합 배열로 했는지 알 수 있을 것이다.
  • 예로 bucket[4]의 의미는 현재 기준 자릿값이 0~4까지 몇 개의 데이터가 있는지 저장한다는 뜻이다
  • 즉 bucket = [1, 2, 3, 3, 6, 9, 9, 9, 11, 11]에서 bucket[4] 뜻은 11 344 372 294 100 24 831 총 6개가 있음을 알려준다
  • 그리고 한 번 output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];로 어떤 a[i]의 값, 예로 들면 344를 일의 자기 기준으로 정렬했다면 => bucket[(A[i] / jarisu) % 10]--;를 해줘서 => bucket = [1, 2, 3, 3, 5, 9, 9, 9, 11, 11]가 된다.
  • 즉 원래 bucket = [1, 2, 3, 3, 6, 9, 9, 9, 11, 11]에서 bucket[4] 뜻은 11 344 372 294 100 24 831 총 6개가 있음을 알려준 거였는데 => 이젠  bucket = [1, 2, 3, 3, 5, 9, 9, 9, 11, 11]가 되어 bucket[4] 뜻은 정렬된 344를 제외하고, 0~4 사이의 수가 총 5개 있음을 알려줌