• 원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라 한다
  • 예를 들어, { 6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 { 2, 5, 7, 8 }
• 일반적으로 최장 증가 부분 수여르이 길이를 구하는 방법은 DP를 이용하는 것

import java.util.Scanner;

public class LIS_DP1 {
    static int N;
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        // 각 위치에서의 LIS를 저장할 1차원 dp 테이블을 정의한다.
        int[] dp = new int[N];
        // 최대 LIS의 값.
        int max = 1;

        // 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
        for (int i = 0; i < N; i++) {
            // 우선 해당 위치를 본인의 길이(1)로 초기화한다.
            dp[i] = 1;
            // 현재 원소의 위치에 대하여, 앞의 원소의 값을 비교하며 값을 갱신한다.
            for (int j = 0; j < i; j++) {
                // 만일 부분 수열이 증가할 가능성이 있다면
                if (arr[j] < arr[i]) {
                    // dp 테이블에 저장된 LIS를 바탕으로 가장 큰 값을 dp[i]의 값으로 갱신한다.
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }

            // 전체 수열에서 LIS의 값을 갱신한다.
            max = Math.max(max, dp[i]);
        }

        System.out.println(max);
        sc.close();
    }
}

위의 코드로 구현하게되면 시간복잡도가 O(N²) 이 되는데 이를 이분탐색을 활용하여 구햔하게 되면 O(NlogN) 의 시간복잡도로 구현할 수 있게 된다

• LIS의 형태를 유지하기 위해 주어진 배열의 인덱스를 하나씩 살펴본다
• 해당 숫자가 들어갈 위치를 이분탐색으로 탐색해 삽입

import java.util.Scanner;

public class LIS_DP2 {
    static int N;
    static int[] arr, dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
        }

        // dp에 실질적으로 저장된 원소의 길이 = LIS인 1차원 dp테이블을 만든다.
        // 해당 dp에 저장된 원소(0이 아닌 값)들은 이후 조사하는 원소들이 부분 수열을 늘릴 수 있을지에 대한 정보를 제공한다.
        dp = new int[N];
        // 처음에 저장된 원소는 없으므로, LIS = 0이다.
        int LIS = 0;

        // 첫 번째 원소부터 N번째 원소까지 dp 테이블의 값을 채워 나간다.
        for (int i = 0; i < N; i++) {
            // 이분 탐색을 활용하여 dp테이블에 저장된 원소를 탐색하며 현재 선택된 숫자가 dp테이블의 어떤 위치에 포함될지 파악한다.
            int idx = BinarySearch(arr[i], 0, LIS, LIS + 1);

            // 찾지 못한 경우
            if(idx == -1) {
                // 가장 마지막 위치에 원소를 삽입하고 LIS의 길이를 늘린다.
                dp[LIS++] = arr[i];
            }
            // 찾은 경우
            else {
                // 해당 위치에 현재 값을 삽입하여 갱신한다.
                dp[idx] = arr[i];
            }
        }

        // LIS의 길이를 출력한다.
        System.out.println(LIS);

        sc.close();
    }

    private static int BinarySearch(int num, int start, int end, int size) {
        int res = 0;
        while (start <= end) {
            // 중앙 값을 찾는다.
            int mid = (start + end) / 2;

            // 만일 현재 선택된 원소가 해당 원소보다 작거나 같다면, 앞 부분을 탐색한다.
            if (num <= dp[mid]) {
                // 해당 원소의 위치를 기억해둔다.
                res = mid;
                end = mid - 1;
            }
            // 만일 현재 선택된 원소가 해당 원소보다 크다면, 뒷 부분을 탐색한다.
            else {
                start = mid + 1;
            }
        }

        // dp테이블에서 삽입될 위치를 찾지 못한 경우(즉, 모든 수들보다 큰 경우).
        if (start == size) {
            return -1;
        }
        // dp테이블에서 삽입될 위치를 찾은 경우.
        else {
            return res;
        }
    }
}

• 해당 방법을 이용하면 최장 증가 부분 수열의 길이는 확실하게 알 수 있지만, 새로 만들어진 배열이 무조건 LIS 가 만들어지는 것은 아니라서 추가적인 작업을 해줘야 한다

출처

• https://sskl660.tistory.com/89
• https://chanhuiseok.github.io/posts/algo-49/

• 한 정점에서 시작해서 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면, 다시 가장 가까운 갈림길로 돌아와서 이곳으로 부터 아직 방문하지 않은 정점을 다른 방향으로 탐색하는 방법
• 모든 정점을 방문하고자 하는 경우 사용
• 어떤 노드를 방문했었는지 여부를 반드시 검사
• 스택 OR 재귀를 이용해 구현
• 너비우선탐색(BFS)보다 더 간단
• 검색 속도는 BFS 보다 느리다

// dfs, 재귀, 인접 행렬, i 정점부터 시작한다.
public static void dfs(int i) {
    visit[i] = true;
    System.out.print(i + " ");

    for(int j=1; j<n+1; j++) {
        if(map[i][j] == 1 && visit[j] == false) {
            dfs(j);
        }
    }
}

• 시간 복잡도
  • 인접 행렬 : O(V²)
  • 인접 리스트 : O(V+E)
• V : 점점, E : 간선

너비 우선 탐색 (Depth First Search)

• 한 정점에서 시작해서 인접한 정점을 모두 방문한 다음 첫번째로 연결 된 정점으로 가서 그것과 연결된 정점들을 방문하고 다음으로 나머지 정점들을 방문하여 동일한 동작을 반복하는 방법
• 두 정점사이에 최단 경로를 찾고자 할 때 사용
• 선입선출 원칙으로 탐색으로 큐를 이용하여 구현

// bfs, q사용, 인접행렬, i 정점부터 시작한다.
public static void bfs(int i) {
    Queue<Integer> q = new LinkedList<>();

    q.offer(i);
    visit[i] = true;

    while(!q.isEmpty()) {
        int temp = q.poll();
        System.out.print(temp + " ");
        for(int j=1; j<n+1; j++) {
            if(map[temp][j] == 1 && visit[j] == false) {
                q.offer(j);
                visit[j] = true;
            }
        }
    }
}

• 시간 복잡도
  • 인접 행렬 : O(V²)
  • 인접 리스트 : O(V+E)
• V : 점점, E : 간선

정리

• 모든 정점을 방문해야하는 문제, 경로의 특징을 저장해야 하는 문제 -> DFS
• 최단경로를 구해야 하는 문제 -> BFS

출처

• https://bbangson.tistory.com/42
• https://velog.io/@soyekwon/%EA%B7%B8%EB%9E%98%ED%94%84-%ED%83%90%EC%83%89-DFSBFS
• https://ko.wikipedia.org/wiki/깊이_우선_탐색
• https://ko.wikipedia.org/wiki/넓이_우선_탐색

• 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다
• 찾고자 하는 값이 속해 있지 않은 부분은 전혀 고려할 필요가 없기 때문에, 매 단계에서 검색해야할 리스트의 크기를 반으로 줄일 수 있다
• 이러한 방법을 반복적으로 사용해 탐색하는 방법이 이분 탐색이다
• 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고, 주로 고정된 데이터에 대한 탐색에 적합하다
• 이분 탐색의 시간복잡도는 O(logN)이 된다

구현

public class BinarySearch {
    static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100};

    public static void main(String[] args) {
        System.out.println("1. 순환 호출을 이용한 이진 탐색");
        System.out.println(binarySearch1(5, 0, arr.length-1)); // 2

        System.out.println("\n2. 반복을 이용한 이진 탐색");
        System.out.println(binarySearch2(20, 0, arr.length-1)); // 6

    }

    // 재귀적 탐색
    static int binarySearch1(int key, int low, int high) {
        int mid;

        if(low <= high) {
            mid = (low + high) / 2;

            if(key == arr[mid]) { // 탐색 성공 
                return mid;
            } else if(key < arr[mid]) {
                return binarySearch1(key ,low, mid-1); // 왼쪽 부분 탐색 
            } else {
                return binarySearch1(key, mid+1, high); // 오른쪽 부분 탐색 
            }
        }

        return -1; // 탐색 실패 
    }

    // 반복적 탐색
    static int binarySearch2(int key, int low, int high) {
        int mid;

        while(low <= high) {
            mid = (low + high) / 2;

            if(key == arr[mid]) {
                return mid;
            } else if(key < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return -1; // 탐색 실패 
    }

}

참고 사이트 : https://minhamina.tistory.com/127

Sorting

• Bubble Sort (거품 정렬)
• Selection Sort (선택 정렬)
• Insertion Sort (삽입 정렬)
• Quick Sort (퀵 정렬)
• Merge Sort (병합 정렬)
• Heap Sort (힙 정렬)
• Radix Sort (기수 정렬)
• Counting Sort (계수 정렬)

Bubble Sort

• 거품 정렬은 바로 옆의 인접한 값과 크기 비교를 하여 조건에 맞춰 정렬을 하는 방식이다.
• 오름차순 정렬의 경우 첫 순환에서 가장 큰 값이 제일 뒤로 가게 되며 그 다음 순환부터는 제일 뒤의 값을 제외하고 크기 비교를 하면 된다.

Complexity

• 시간복잡도
  • 최선 : O(N²)
  • 평균 : O(N²)
  • 최악 : O(N²)
• 정렬이 돼있던 안돼있던, 2개의 원소를 무조건 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(N²)

Code

void bubbleSort(int[] arr) { // Ascending
    int temp = 0;
    for (int i = 0; i < arr.length; i++)      
        for (int j = 0; j < arr.length - i - 1; j++)
            if(arr[j] > arr[j + 1])
                swap(array, j, j + 1);
}

Pros & Cons

• 구현이 매우 간단하고 소스코드가 직관적
• 추가적인 메모리 공간을 필요로 하지 않음
• 안정 정렬(Stable Sort)
• 시간복잡도가 O(N²)으로 비효율적

Selection Sort

• 선택 정렬은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘
• 주어진 배열 중의 최솟값을 찾아 맨앞의 위치값과 교체하고, 다음 순환에서 맨처음 위치를 뺀 나머지 배열을 같은 방법으로 교체

Complexity

• 시간복잡도
  • 최선 : O(N²)
  • 평균 : O(N²)
  • 최악 : O(N²)
• 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 배열을 정렬하는데 O(N²)

Code

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length - 1; i++) {       
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++)  
            if (arr[j] < arr[indexMin])            
                indexMin = j;

        swap(arr[indexMin], arr[i]);
  }
}

Pros & Cons

• 구현이 매우 간단하고 소스코드가 직관적
• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적
• 추가적인 메모리 공간을 필요로 하지 않음
• 시간복잡도가 O(N²)으로 비효율적
• 불안정 정렬(Unstable Sort) : 중복된 값의 인덱스의 순서가 바뀐다

Insertion Sort

• 삽입 정렬은 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘
• 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘

Complexity

• 시간복잡도
  • 최선 : O(N)
  • 평균 : O(N²)
  • 최악 : O(N²)
• 정렬이 돼있으면 최선의 경우로 O(N)의 시간복잡도를 갖게 됨

Code

void insertionSort(int[] arr)
{
   for(int index = 1 ; index < arr.length ; index++){
      int temp = arr[index];
      int prev = index - 1;
      while( (prev >= 0) && (arr[prev] > temp) ) {    
         arr[prev+1] = arr[prev];
         prev--;
      }
      arr[prev + 1] = temp;                           
   }
}
}

Pros & Cons

• 알고리즘이 단순하다
• 대부분의 원소가 정렬되어 있는 경우 매우 효율적
• • 안정 정렬(Stable Sort)
• 평균과 최악의 시간복잡도가 O(N²)으로 비효율적
• 배열의 길이가 길어질수록 비효율적

Quick Sort

• 퀵 소트는 분할 정복(Divide & Conquer) 방법 을 통해 주어진 배열을 정렬
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
• 합병 정렬과 달리 퀵 소트는 배열을 비균등하게 분할
• 배열 가운데서 하나의 원소, 피벗(pivot)을 고른다
• 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.
• 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다
• 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다
• 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복
• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

Complexity

• 시간복잡도
  • 최선 : O(Nlog₂N)
  • 평균 : O(Nlog₂N)
  • 최악 : O(N²)
• 최선의 경우에 순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산으로 O(Nlog₂N)가 된다
  • 배열의 크기가 n(n = 2³) 이면 2³ -> 2² -> 2¹ -> 2⁰ 으로 줄어들어 재귀 호출의 깊이가 3이 되고 일반화 하면 n = 2ᴷ인 경우 k = log₂n 임을 알 수 있다
• 최악의 경우 배열이 오름차순 정렬 또는 내림차순 정렬이 되어있는 경우인데 이때는 재귀호출의 깊이가 N이 되어 시간복잡도가 O(N²)이 된다

Code

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;

    // 분할 
    int pivot = partition(); 

    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

public int partition(int[] array, int left, int right) {
    /**
    // 최악의 경우, 개선 방법
    int mid = (left + right) / 2;
    swap(array, left, mid);
    */

    int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;

    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;

    return i;
}

Pros & Cons

• 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(Nlog₂N)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠름

• 다른 메모리 공간을 필요로 하지 않음

• 불안정 정렬(Unstable Sort)

• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸림

• JAVA에서 Arrays.sort() 내부적으로도 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘

• Dual Pivot Quick Sort

  • 삽입 정렬(Insertion Sort)와 Quick Sort를 합친 것

  • 피봇을 2개 사용함으로써 3개의 영역으로 나누는 것이 핵심

  • 배열의 가장 왼쪽 항목은 lp로, 가장 오른쪽 항목은 rp로 설정

  • lp> rp 인 경우 lp와 rp를 바꾸어준다

  • lp와 rp를 이용하여 다시 세 개의 영역으로 분할

    void DualPivotQuickSort(int arr[], int left, int right){
    // lp : Left Pivot, rp : Right Pivot
    
    // left > right인 경우는 배열상으로 성립이 되지 않는다.
    if(left <= right){
      int lp = arr[left]; // 분할의 가장 왼쪽 값
      int rp = arr[right]; // 분할의 가장 오른쪽 값
    
      // 양 끝의 값을 비교한다.
      if(arr[lp] > arr[rp]){
          swap(arr, lp, rp); // lp가 크면 lp와 rp의 위치를 바꾸어준다. 
      }
    
      int l = left + 1; 
      int k = left + 1; // left+1의 원소부터 차례로 비교해준다.
      int g = right - 1;
    } 
    
    while(k <= g){ //서로 엇갈릴 때 까지
      //arr[k]가 lp보다 작으면, lp보다 작은 (1)영역에 들어간다.
      if(arr[k] < lp){
          swap(arr, k, l);
          l++;
      }
    
      // lp보다 큰 (2)영역, (3)영역
      else{
          //rp보다 큰 (3) 영역
          if(arr[k] > rp){
              while(arr[g] > rp && k < g){
                  g--;
              }
              swap(arr, k, g);
              g--;
    
              if(arr[k] < lp){
                  swap(arr, k, l);
                  l++;
              }
          }
      }
    
      k++; // k에 대한 비교가 끝
    }
    
    l--; g--;
    swap(arr, left, l);
    swap(arr, right, r);
    DualPivotQuickSort(arr, left, l-1);
    DualPivotQuickSort(arr, l+1, g-1);
    DualPivotQuickSort(arr, g+1, right);
    }

Merge Sort

• 합병 정렬은 퀵 소트와 마찬가지로 분할 정복(Divide & Conquer) 방법 을 통해 주어진 배열을 정렬
• 퀵 소트와 반대로 안정 정렬에 속함
• 퀵 소트와의 차이점
  • 퀵 소트 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)
  • 합병 정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)
• 주의할 점은 합병 정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다
• 어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이며, 보통 아래와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라 함

Complexity

• 시간복잡도
  • 최선 : O(Nlog₂N)
  • 평균 : O(Nlog₂N)
  • 최악 : O(Nlog₂N)
• 정렬이 돼있던 안돼있던, 2개의 원소를 무조건 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간복잡도가 O(N²)

Code

public void mergeSort(int[] array, int left, int right) {

    if(left < right) {
        int mid = (left + right) / 2;

        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }

}

public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);

    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;

    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }

    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

Pros & Cons

• 합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적이다
  • LinkedList는 삽입, 삭제 연산에서 유용하지만 접근 연산에서는 비효율적
  • 따라서 임의로 접근하는 퀵 소트를 활용하면 오버헤드 발생이 증가
• 배열의 클경우 원소들의 이동횟수가 많아 느림

Heap Sort

• 완전이진트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식
  • 완전이진트리 : 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리
  • 힙(Heap)
    • 완전이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
    • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
    • 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다

Complexity

• 시간복잡도
  • 최선 : O(Nlog₂N)
  • 평균 : O(Nlog₂N)
  • 최악 : O(Nlog₂N)
• heapify 함수의 시간복잡도가 log₂N 이고 모든 노드마다 실행되면 전체의 시간복잡도는 Nlog₂N 이 된다

Code

public static void heapify(int array[], int n, int i) {
    int p = i;
    int l = i * 2 + 1;
    int r = i * 2 + 2;

    if (l < n && array[p] < array[l]) {
        p = l;
    }

    if (r < n && array[p] < array[r]) {
        p = r;
    }

    if (i != p) {
        swap(array, p, i);
        heapify(array, n, p);
    }
}

public static void heapSort(int[] array) {
    int n = array.length;

    // init, max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(array, n, i);
    }

    // for extract max element from heap
    for (int i = n - 1; i > 0; i--) {
        swap(array, 0, i);
        heapify(array, i, 0);
    }
}

Pros & Cons

• Heap Sort가 유용할 때
  • 가장 크거나 가장 작은 값을 구할 때 (최소 힙 또는 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능)
  • 최대 k 만큼 떨어진 요소들을 정렬할 때 (삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음)
• 불안정 정렬(Unstable Sort) : 중복된 값의 인덱스의 순서가 바뀐다

Counting Sort

• 카운팅 정렬의 기본 매커니즘은 아주 단순하게 데이터의 값이 몇 번 나왔는지를 세어 주는 것이다
• 과정
  1. array 를 한 번 순회하면서 각 값이 나올 때마다 해당 값을 index 로 하는 새로운 배열(counting)의 값을 1 증가시킨다
  2. counting 배열 값들을 누적합으로 설정한다 (counting 배열의 각 값은 (시작점 - 1)을 알려준다)
  3. countin[i] 의 값에 1 을 빼준 뒤 해당 값이 새로운 배열의 인덱스 [해당값 - 1]에 위치하게 된다.

Complexity

• 시간복잡도
  • 최선 : O(N + K)
  • 평균 : O(N + K)
  • 최악 : O(N + K)
• K는 배열에서 등장하는 최댓값
• 데이터를 직접 비교하는 알고리즘이 아니기 때문에 O(N) 의 시간 복잡도

Code

int arr[5];         // [5, 4, 3, 2, 1]
int sorted_arr[5];
// 과정 1 - counting 배열의 사이즈를 최대값 5가 담기도록 크게 잡기
int counting[6];    // 단점 : counting 배열의 사이즈의 범위를 가능한 값의 범위만큼 크게 잡아야 하므로, 비효율적이 됨.

// 과정 2 - counting 배열의 값을 증가해주기.
for (int i = 0; i < arr.length; i++) {
    counting[arr[i]]++;
}
// 과정 3 - counting 배열을 누적합으로 만들어주기.
for (int i = 1; i < arr.length; i++) {
    counting[i] += counting[i - 1];
}
// 과정 4 - 뒤에서부터 배열을 돌면서, 해당하는 값의 인덱스에 값을 넣어주기.
for (int i = arr.length - 1; i >= 0; i--) {
    sorted_arr[counting[arr[i]]] = arr[i];
    counting[arr[i]]--;
}

Pros & Cons

• 두 데이터를 비교하는 과정이 없기 때문에 굉장히 짧은 시간복잡도를 가진다
• 하지만 수열의 길이보다 수의 범위가 굉장히 커지면 그 범위만큼의 배열을 생성해야하기 때문에 메모리가 매우 낭비된다

Radix Sort

• 계수 정렬(Counting Sort)과 마찬가지로 비교연산을 수행하지 않아 조건이 맞는 상황에서 빠른 정렬 속도를 보장하는 알고리즘
• 데이터의 각 자릿수를 낮은 자리수에서부터 가장 큰 자리수까지 올라가면서 정렬을 수행하는 것
• 자릿수가 존재하지 않는 데이터를 기수정렬로 정렬하는 것은 불가능
• 과정 (가장 큰 자리수가 100의 자리일 때)
  • 각 데이터들의 1의 자리를 비교해서 같은 데이터끼리 모은다 (1의 자리가 작은 데이터들이 앞에 위치하게 되고 큰 숫자들이 뒤에 위치하게 된다) (오름차순 기준)
  • 이때 같은 자릿수에 여러 데이터가 있을 경우에는 입력된 순서(나열된 순서)로 데이터를 모은다
  • 2번까지 과정을 마치면 1의 자리가 가장 작은 숫자부터 가장 큰 숫자 순으로 데이터들이 정렬된다.
  • 이번에는 10의 자리가 같은 데이터끼리 오름차순으로 나열한다.
  • 10보다 작은 숫자들은 배열에 위치했던 순서대로 새로운 정렬의 제일 앞에 위치하게 된다.
  • 이번에는 100의 자리가 같은 데이터끼리 오름차순으로 나열한다.
  • 100보다 작은 숫자들은 배열의 제일 앞에서부터 순서대로 채운다.
  • 데이터들의 최대 자릿수가 100의 자리이기 때문에 더 이상 진행하지 않고 종료한다.

Complexity

• 시간복잡도
  • 최선 : O(N + K)
  • 평균 : O(N + K)
  • 최악 : O(N + K)
• K는 배열에서 등장하는 가장 큰 기수

Code

void countSort(int arr[], int n, int exp) {
    int buffer[n];
    int i, count[10] = {0};

    // exp의 자릿수에 해당하는 count 증가
    for (i = 0; i < n; i++){
        count[(arr[i] / exp) % 10]++;
    }
    // 누적합 구하기
    for (i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    // 일반적인 Counting sort 과정
    for (i = n - 1; i >= 0; i--) {
        buffer[count[(arr[i]/exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    for (i = 0; i < n; i++){
        arr[i] = buffer[i];
    }
}

void radixsort(int arr[], int n) {
     // 최댓값 자리만큼 돌기
    int m = getMax(arr, n);

    // 최댓값을 나눴을 때, 0이 나오면 모든 숫자가 exp의 아래
    for (int exp = 1; m / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

Pros & Cons

• MSD (Most-Significant-Digit) 과 LSD (Least-Significant-Digit)
  • MSD는 가장 큰 자리수부터 Counting sort 하는 것을 의미하고, LSD는 가장 낮은 자리수부터 Counting sort 하는 것을 의미
  • LSD의 경우 Digit의 갯수만큼 따져야하는 단점이 있지만 그에 반해 MSD는 마지막 자리수까지 확인해 볼 필요가 없이 중간에 결과를 알 수 있다
  • 따라서 MSD를 사용하면 시간을 줄일 수 있으나 정렬이 되었는지 확인하는 과정이 필요하고, 이 때문에 메모리를 더 사용하게 된다
  • LSD는 알고리즘이 일관됨 (Branch Free algorithm) 그러나 MSD는 일관되지 못함 --> 따라서 Radix sort는 주로 LSD를 언급함
  • LSD는 자릿수가 정해진 경우 좀 더 빠를 수 있다

참조 : https://hanhyx.tistory.com/35, https://gyoogle.dev/blog/algorithm/Bubble%20Sort.html, https://cs-vegemeal.tistory.com/53, https://st-lab.tistory.com/233?category=892973

키패드 누르기

📝 Solution

• 손가락의 좌표와 키패드의 좌표를 나타내는 Key Class 구현
• 왼속가락의 좌표, 오른손가락의 좌표, 손잡이의 정보를 가진 Hand Class 구현
• 키패드를 Map을 이용해 <숫자, 좌표> 로의 형식으로 구현
• 3으로 나눈 나머지로 구분하여 왼쪽, 가운데, 오른쪽을 구분해 해당 조건에 맞게 StringBuilder에 추가

        private void move(int num, Hand hand, StringBuilder builder) {
            // Right Side
            if (num % 3 == 0 && num != 0) {
                hand.rightFinger.moveFinger(keypad.get(num));
                builder.append("R");
            }

            // Left Side
            else if (num % 3 == 1) {
                hand.leftFinger.moveFinger(keypad.get(num));
                builder.append("L");
            }

            // Center
            else {
                if (hand.rightFinger.getDistance(keypad.get(num))
                        < hand.leftFinger.getDistance(keypad.get(num))) {
                    hand.rightFinger.moveFinger(keypad.get(num));
                    builder.append("R");
                }

                else if (hand.rightFinger.getDistance(keypad.get(num))
                        > hand.leftFinger.getDistance(keypad.get(num))) {
                    hand.leftFinger.moveFinger(keypad.get(num));
                    builder.append("L");
                }

                else {
                    if (hand.isRightHanded()) {
                        hand.rightFinger.moveFinger(keypad.get(num));
                        builder.append("R");
                    }

                    else {
                        hand.leftFinger.moveFinger(keypad.get(num));
                        builder.append("L");
                    }
                }
            }
        }

💻 Code

Solution.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    static class Key {
        int r;
        int c;

        public Key(int r, int c) {
            this.r = r;
            this.c = c;
        }

        public void moveFinger(Key key) {
            this.r = key.r;
            this.c = key.c;
        }

        public int getDistance(Key key) {
            return Math.abs(this.r - key.r) + Math.abs(this.c - key.c);
        }
    }

    static class Hand {
        Key leftFinger;
        Key rightFinger;
        String handed;

        public Hand(String handed) {
            this.leftFinger = new Key(3, 0);
            this.rightFinger = new Key(3, 2);
            this.handed = handed;
        }

        public boolean isRightHanded() {
            return this.handed.equals("right");
        }
    }

    static Map<Integer, Key> keypad = new HashMap<>();

    public String solution(int[] numbers, String hand) {
        StringBuilder answer = new StringBuilder();
        Hand h = new Hand(hand);

        setKeypad();

        for (int num : numbers)
            move(num, h, answer);

        return answer.toString();
    }

    private void setKeypad() {
        keypad.put(0, new Key(3, 1));
        keypad.put(1, new Key(0, 0));
        keypad.put(2, new Key(0, 1));
        keypad.put(3, new Key(0, 2));
        keypad.put(4, new Key(1, 0));
        keypad.put(5, new Key(1, 1));
        keypad.put(6, new Key(1, 2));
        keypad.put(7, new Key(2, 0));
        keypad.put(8, new Key(2, 1));
        keypad.put(9, new Key(2, 2));
    }

    private void move(int num, Hand hand, StringBuilder builder) {
        // Right Side
        if (num % 3 == 0 && num != 0) {
            hand.rightFinger.moveFinger(keypad.get(num));
            builder.append("R");
        }

        // Left Side
        else if (num % 3 == 1) {
            hand.leftFinger.moveFinger(keypad.get(num));
            builder.append("L");
        }

        // Center
        else {
            if (hand.rightFinger.getDistance(keypad.get(num))
                    < hand.leftFinger.getDistance(keypad.get(num))) {
                hand.rightFinger.moveFinger(keypad.get(num));
                builder.append("R");
            }

            else if (hand.rightFinger.getDistance(keypad.get(num))
                    > hand.leftFinger.getDistance(keypad.get(num))) {
                hand.leftFinger.moveFinger(keypad.get(num));
                builder.append("L");
            }

            else {
                if (hand.isRightHanded()) {
                    hand.rightFinger.moveFinger(keypad.get(num));
                    builder.append("R");
                }

                else {
                    hand.leftFinger.moveFinger(keypad.get(num));
                    builder.append("L");
                }
            }
        }
    }
}

17143 낚시왕

📝 Solution

Key Idea

• 다른 시뮬레이션 문제들과 유사하게 조건에 부합하게 구현만 하면 된다
• 주의해야할 점은 상어를 삭제할 때 이동을 모두 끝낸 후에 해당되는 상어를 제거해야되는 것이다
• 처음에는 상어들의 목록을 ArrayList 를 이용해 구현했었는데 그러면 상어를 삭제할때마다 index 가 변경되어 상어 Class 에 num field를 따로 두어 제거할 상어를 찾을 때 계속해서 num 을 이용해 index를 찾아야하는 불편함이 있었다
• 위를 해결하기 위해 Map 을 이용해 상어의 num 을 key 값, 상어 class 를 value 로 두어 코드를 간략화했고 소요 시간도 감소할 줄 알았으나...
• 메모리 사용량은 거의 2배로 뛰고 시간도 조금 더 걸렸다...
• 두 자료형에서 get 을 할때의 소요시간이 더 걸리는 것인지 파라미터로 넘길 때에 메모리의 사용량에서 차이가 있는지 한번 알아봐야 할 것 같다

        int sizeSum = 0;
        int[][] location = new int[R + 1][C + 1];
        Map<Integer, Shark> map = new HashMap<>();

        for(int[] row : location)
            Arrays.fill(row, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            Shark shark = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            map.put(i, shark);
            location[shark.r][shark.c] = i;
        }

        for (int i = 1; i <= C; i++) {
            int num = findNearest(location, R, i);

            if (num != -1) {
                Shark shark = map.get(num);
                sizeSum += shark.z;
                location[shark.r][shark.c] = -1;
                map.remove(num);
            }
            move(R, C, map, location);
        }

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Shark {
    int r;
    int c;
    int s;
    int d;
    int z;

    public Shark(int r, int c, int s, int d, int z) {
        this.r = r;
        this.c = c;
        this.s = s;
        this.d = d;
        this.z = z;
    }

    public void changeDir() {
        switch (this.d) {
            case 1:
                this.d = 2;
                break;
            case 2:
                this.d = 1;
                break;
            case 3:
                this.d = 4;
                break;
            case 4:
                this.d = 3;
        }
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int sizeSum = 0;
        int[][] location = new int[R + 1][C + 1];
        Map<Integer, Shark> map = new HashMap<>();

        for(int[] row : location)
            Arrays.fill(row, -1);

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            Shark shark = new Shark(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            map.put(i, shark);
            location[shark.r][shark.c] = i;
        }

        for (int i = 1; i <= C; i++) {
            int num = findNearest(location, R, i);

            if (num != -1) {
                Shark shark = map.get(num);
                sizeSum += shark.z;
                location[shark.r][shark.c] = -1;
                map.remove(num);
            }
            move(R, C, map, location);
        }

        System.out.println(sizeSum);
    }

    private static int findNearest(int[][] location, int R, int C) {
        int sharkNum = -1;

        for (int i = 1; i <= R; i++)
            if(location[i][C] != -1) {
                sharkNum = location[i][C];
                break;
            }
        return sharkNum;
    }

    private static boolean isOutOfBound(int x, int y, int R, int C) {
        return x == 0 || y == 0 || x > R || y > C;
    }

    private static void move(int R, int C, Map<Integer, Shark> map, int[][] location) {
        int[] dx = {0, -1, 1, 0, 0};
        int[] dy = {0, 0, 0, 1, -1};

        for (Shark shark : map.values()) {
            int direction = shark.d, distance = shark.s;
            int x = shark.r, y = shark.c;
            location[x][y] = -1;

            while (distance > 0) {
                if (isOutOfBound(x + dx[direction], y + dy[direction], R, C)) {
                    shark.changeDir();
                    direction = shark.d;
                }

                x += dx[direction];
                y += dy[direction];

                distance--;
            }
            shark.r = x;
            shark.c = y;
        }

        ArrayList<Integer> removeList = new ArrayList<>();

        for (int num : map.keySet()) {
            Shark shark = map.get(num);
            if (location[shark.r][shark.c] != -1) {
                Shark original = map.get(location[shark.r][shark.c]);

                if (original.z > shark.z)
                    removeList.add(num);
                else {
                    removeList.add(location[shark.r][shark.c]);
                    location[shark.r][shark.c] = num;
                }
            }
            else
                location[shark.r][shark.c] = num;
        }

        for(int num : removeList)
            map.remove(num);
    }
}

12919 A와 B 2

📝 Solution

Key Idea

• S를 T로 바꾸는 것이 아닌 T를 S로 바꾼다
• 이전 A와 B 문제와의 차이점은 B를 먼저 추가하고 문자열을 뒤집는 것인데
• 이렇게되면 B・・・A와 같은 경우에 연산 2가지중 어느것을 먼저 수행해야할지 우선순위가 정해져 있지 않다
• 그러므로 모든 경우의 수를 탐색하기위해 DFS 를 사용한다
• 문자열을 뒤집는 연산은 실제로 하지는 않고 boolean 값을 이용해 판단한다
• DFS 를 사용해 종료 조건을 문자열의 길이가 같아질때 까지로 두고
• head가 어딘지에 따라 문자열을 비교하여 확인한다

private static void DFS(String S, String T, boolean head) {
    if (T.length() == S.length()) {
        if(T.equals(S) && head || reverse(T).equals(S) && !head)
            check = true;
        return;
    }

    if (head) {
        if(T.charAt(T.length() - 1) == 'A')
            DFS(S, T.substring(0, T.length() - 1), true);
        if(T.charAt(0) == 'B')
            DFS(S, T.substring(1), false);
    }

    else {
        if(T.charAt(0) == 'A')
            DFS(S, T.substring(1), false);
        if(T.charAt(T.length() - 1) == 'B')
            DFS(S, T.substring(0, T.length() - 1), true);
    }
}

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    private static boolean check = false;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();

        DFS(S, T, true);

        if(check)
            System.out.println(1);
        else
            System.out.println(0);
    }

    private static String reverse(String T) {
        StringBuilder builder = new StringBuilder(T);
        return builder.reverse().toString();
    }

    private static void DFS(String S, String T, boolean head) {
        if (T.length() == S.length()) {
            if(T.equals(S) && head || reverse(T).equals(S) && !head)
                check = true;
            return;
        }

        if (head) {
            if(T.charAt(T.length() - 1) == 'A')
                DFS(S, T.substring(0, T.length() - 1), true);
            if(T.charAt(0) == 'B')
                DFS(S, T.substring(1), false);
        }

        else {
            if(T.charAt(0) == 'A')
                DFS(S, T.substring(1), false);
            if(T.charAt(T.length() - 1) == 'B')
                DFS(S, T.substring(0, T.length() - 1), true);
        }
    }
}

2866 문자열 잘라내기

📝 Solution

Key Idea

• 입력받은 문자열들의 세로로 문자열들을 넣은 List 를 최초에 한번만 생성
• 가장 위의 행을 제외한 세로 문자열들에 중복이 없다면
• 실제로 문자열 하나를 삭제하는 것이 아닌 idx 를 증가시켜 세로 문자열들의 앞에서 하나씩 잘라준다
• 중복검사는 세로 문자열들을 Map 에 key 로 넣고 value는 개수로 둬서
• 만약 value 가 2이상이라면 중복이 발생한 것이므로 count 개수를 출력하고 프로그램을 종료한다
• 중복이 발생하지 않았다면 count++ 하고 idx++ 해주어 가장위의 행을 지운 것과 같은 효과를 본다

    private static boolean isDup(ArrayList<String> list, int idx) {
        Map<String, Integer> map = new HashMap<>();

        for (String col : list){
            col = col.substring(idx);
            map.put(col, map.getOrDefault(col, 0) + 1);

            if (map.get(col) >= 2)
                return true;
        }
        return false;
    }

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        int count = 0, idx = 1;
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        ArrayList<String> list = new ArrayList<>();

        for(int i = 0; i < R; i++)
            list.add(br.readLine());

        ArrayList<String> colStrings = makeCols(list, C);

        while (true) {
            if (isDup(colStrings, idx)) {
                System.out.println(count);
                break;
            } else {
                count++;
                idx++;
            }
        }
    }

    private static ArrayList<String> makeCols(ArrayList<String> list, int C) {
        ArrayList<String> temp = new ArrayList<>();

        for (int i = 0; i < C; i++) {
            StringBuilder builder = new StringBuilder();

            for (String s : list)
                builder.append(s.charAt(i));

            temp.add(builder.toString());
        }
        return temp;
    }
    private static boolean isDup(ArrayList<String> list, int idx) {
        Map<String, Integer> map = new HashMap<>();

        for (String col : list){
            col = col.substring(idx);
            map.put(col, map.getOrDefault(col, 0) + 1);

            if (map.get(col) >= 2)
                return true;
        }
        return false;
    }
}

12904 A와 B

📝 Solution

Key Idea

• A를 추가하는 연산과 문자열을 뒤집고 뒤에 B를 추가하는 연산을 거꾸로 생각한다
• T 에서 위의 연산들을 거꾸로 실행하여 S가 되는지 검사한다
• 문자열을 뒤집는 과정은 boolean 을 전역변수로 선언하여 head 쪽이 앞이면 true, tail 쪽이 앞이면 false 로 생각한다
• T 문자열의 맨뒤에 있는 Char 를 검사하여 A 면 그냥 제거만하고 B 이면 제거를 한 후에 boolean 값을 바꿔준다
• 연산을 거치다가 T 문자열의 길이와 S 문자열의 길이가 같아졌을 때 equals() 검사를 한다

private static String remove(String T) {
    if(head){
        if (T.charAt(T.length() - 1) == 'B')
            head = false;
        return T.substring(0, T.length() - 1);
    }
    else {
        if (T.charAt(0) == 'B')
            head = true;
        return T.substring(1);
    }
}

💻 Code

import java.util.Scanner;

public class Main {
    private static boolean head;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String S = scanner.next();
        String T = scanner.next();
        head = true;

        while (S.length() < T.length())
            T = remove(T);

        if(!head)
            T = reverse(T);

        if(S.equals(T))
            System.out.println(1);
        else
            System.out.println(0);

        scanner.close();
    }

    private static String remove(String T) {
        if(head){
            if (T.charAt(T.length() - 1) == 'B')
                head = false;
            return T.substring(0, T.length() - 1);
        }
        else {
            if (T.charAt(0) == 'B')
                head = true;
            return T.substring(1);
        }
    }

    private static String reverse(String T) {
        StringBuilder builder = new StringBuilder(T);
        return builder.reverse().toString();
    }
}

9935 문자열 폭발

📝 Solution

Key Idea

• target 문자열에서 한 글자씩 StringBuilder에 넣는다
• builder 의 길이가 Bomb 문자열보다 길어졌을때 부터,
• 한글자씩 비교하며 만약 같다면 바로바로 그 문자열을 삭제해 준다

for (int i = 0; i < target.length(); i++) {
    char c = target.charAt(i);

    builder.append(c);

    if (builder.length() >= bomb.length()) {
        boolean check = true;

        for (int j = 0; j < bomb.length(); j++) {
            char targetC = builder.charAt(builder.length() - bomb.length() + j);
            char bombC = bomb.charAt(j);

            if (targetC != bombC) {
                check = false;
                break;
            }
        }

        if (check)
            builder.delete(builder.length() - bomb.length(), builder.length());
    }
}

💻 Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String target = scanner.next();
        String bomb = scanner.next();
        StringBuilder builder = new StringBuilder();

        for (int i = 0; i < target.length(); i++) {
            char c = target.charAt(i);

            builder.append(c);

            if (builder.length() >= bomb.length()) {
                boolean check = true;

                for (int j = 0; j < bomb.length(); j++) {
                    char targetC = builder.charAt(builder.length() - bomb.length() + j);
                    char bombC = bomb.charAt(j);

                    if (targetC != bombC) {
                        check = false;
                        break;
                    }
                }

                if (check)
                    builder.delete(builder.length() - bomb.length(), builder.length());
            }
        }

        if(builder.length() == 0)
            System.out.println("FRULA");
        else
            System.out.println(builder);

        scanner.close();
    }
}

5430 AC

📝 Solution

Key Idea

• 문자열에서 숫자만 분리하여 ArrayList 에 담는다
• R 연산을 할때에는 실제로 배열을 reverse 하는 것이 아닌 정방향과 역방향으로 boolean 값으로 구분한다
• 배열의 size 가 0 일 때 D 연산을 수행한다면 error 반환
• 배열의 size 가 1 이상 일 떄 정방향 역방향에 따라 배열을 제거하는 인덱스를 0 또는 length - 1 로 한다

private static String execute(String functions, ArrayList<Integer> list) {
    boolean check = true; // true : 정방향 , false : 역방향

    for (int i = 0; i < functions.length(); i++) {
        char function = functions.charAt(i);

        if (function == 'R')
            check = !check;

        else {
            if (list.size() == 0)
                return "error";
            if (check)
                list.remove(0);
            else
                list.remove(list.size() - 1);
        }
    }

    return makeArray(list, check);
}

💻 Code

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();

        for (int i = 0; i < T; i++) {
            String functions = scanner.next();
            int n = scanner.nextInt();
            String array = scanner.next();

            ArrayList<Integer> list = numArray(array);
            System.out.println(execute(functions, list));
        }

        scanner.close();
    }

    private static ArrayList<Integer> numArray(String ary) {
        ArrayList<Integer> num = new ArrayList<>();
        String[] tokens = ary.substring(1, ary.length() - 1).split(",");

        if(tokens[0].equals(""))
            return num;

        for(String token : tokens)
            num.add(Integer.parseInt(token));

        return num;
    }

    private static String execute(String functions, ArrayList<Integer> list) {
        boolean check = true; // true : 정방향 , false : 역방향

        for (int i = 0; i < functions.length(); i++) {
            char function = functions.charAt(i);

            if (function == 'R')
                check = !check;

            else {
                if (list.size() == 0)
                    return "error";
                if (check)
                    list.remove(0);
                else
                    list.remove(list.size() - 1);
            }
        }

        return makeArray(list, check);
    }

    private static String makeArray(ArrayList<Integer> list, boolean check) {
        StringBuilder builder = new StringBuilder();

        builder.append("[");

        if (check) {
            for (int i = 0; i < list.size(); i++) {
                if (i == 0)
                    builder.append(list.get(i));
                else
                    builder.append(",").append(list.get(i));
            }
        }

        else {
            for (int i = list.size() - 1; i >= 0; i--) {
                if (i == list.size() - 1)
                    builder.append(list.get(i));
                else
                    builder.append(",").append(list.get(i));
            }
        }

        builder.append("]");

        return builder.toString();
    }
}

1541 잃어버린 괄호

📝 Solution

Key Idea

• 덧셈은 괄호의 영향을 받지 않으나 뺄셈은 괄호의 영향을 받는다
• 그래서 덧셈을 다한 후에 뺄셈을 진행하게되면 가장 큰수를 뺄 수 있다
• - 로 분리한것들을 더한뒤에 빼기 연산을 해줄때 가장 앞의 숫자는 양수이므로 덧셈을 해준다

String expr = scanner.next();

String[] minusToken = expr.split("-");

for (int i = 0; i < minusToken.length; i++) {
    int plusNum = 0;

    String[] plusToken = minusToken[i].split("\\+");

    for(String plus : plusToken)
        plusNum += Integer.parseInt(plus);

    if(i == 0)
        answer += plusNum;
    else
        answer -= plusNum;
}

💻 Code

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int answer = 0;
        Scanner scanner = new Scanner(System.in);

        String expr = scanner.next();

        String[] minusToken = expr.split("-");

        for (int i = 0; i < minusToken.length; i++) {
            int plusNum = 0;

            String[] plusToken = minusToken[i].split("\\+");

            for(String plus : plusToken)
                plusNum += Integer.parseInt(plus);

            if(i == 0)
                answer += plusNum;
            else
                answer -= plusNum;
        }

        System.out.println(answer);

        scanner.close();
    }
}

입국심사

• 처음에 모든 심사대는 비어있습니다
• 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다
• 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다
• 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다
• 모든 사람이 심사를 받는데 걸리는 최소 시간 찾기

📝 Solution

Key Idea

• 각 심사관이 걸리는 시간의 배열을 오름차순 정렬합니다
• left 에 0 과 right 에 가장 시간이 오래 걸리는 최악의 경우인 times[times.length - 1] * n 을 넣습니다
• 두 시간의 중간 지점인 mid 로 각 심시관들이 mid 시간동안 심사할 수 있는 사람의 수를 sum 에 모두 더해줍니다
• 만약 sum 이 심사를 받아야할 사람수 n 보다 작을 경우 시간을 더 늘려야 하기 때문에 left 에 mid + 1 을 넣고 오른쪽으로 다시 이분탐색 합니다
• 그렇지 않다면, 해당 시간에 모든 사람을 심사할 수 있으므로 answer 에 mid 시간을 넣어주고, right 에 mid - 1 을 넣고 왼쪽으로 다시 이분 탐색하여 최소의 시간을 찾습니다

while (left <= right) {
    mid = (left + right) / 2;

    long sum = 0;

    for (int time : times)
        sum += mid / time;

    if (sum < n)
        left = mid + 1;

    else {
        right = mid - 1;
        answer = mid;
    }
}

💻 Code

Solution.java

import java.util.Arrays;

class Solution {
    public long solution(int n, int[] times) {
        long answer = Long.MAX_VALUE;

        Arrays.sort(times);

        long left = 0, mid, right = (long) times[times.length - 1] * n;

        while (left <= right) {
            mid = (left + right) / 2;

            long sum = 0;

            for (int time : times)
                sum += mid / time;

            if (sum < n)
                left = mid + 1;

            else {
                right = mid - 1;
                answer = mid;
            }
        }

        return answer;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        long result = solution.solution(6, new int[]{7, 10});
        assertEquals(28, result);
    }

    @Test
    public void solution_2(){
        long result = solution.solution(10, new int[]{6, 8, 10});
        assertEquals(30, result);
    }
}

N으로 표현

• 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값 찾기

📝 Solution

Key Idea

• DP 를 사용하기 위해 1~8 인덱스까지의 HashSet 배열을 만듭니다
• 먼저 N 이 number 과 같은 경우를 처리하여 1을 리턴해 줍니다
• 그리고 2번째 인덱스 부터 이전의 인덱스의 HashSet 의 값들을 가지고 사칙연산을 진행하여 add 해줍니다
  • 예를 들어 [5]의 값을 구하기 위해 [1]-[4], [2]-[3], [3]-[2], [4]-[1] 의 값들을 각각 사칙연산하여 값을 저장해 줍니다
• 여기서 각 HashSet에 맨처음 인덱스의 수만큼의 N들로 이루어진 수를 더해주고
• 나누기 연산에서 divide by zero 를 생각하여 나누는 수가 0인 경우를 제외해 줍니다

    public int solution(int N, int number) {
        int answer = -1;

        if(N == number)
            return 1;

        Set<Integer>[] dp = new Set[9];

        for (int i = 0; i <= 8; i++)
            dp[i] = new HashSet<>();

        dp[1].add(N);

        for (int i = 2; i <= 8; i++){
            dp[i].add(makeNstr(N, i));

            for (int j = 1; j <= i - 1; j++)
                for(int k : dp[j])
                    for(int h : dp[i - j])
                        calculation(dp, i, k, h);


            if (dp[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }

💻 Code

Solution.java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int N, int number) {
        int answer = -1;

        if(N == number)
            return 1;

        Set<Integer>[] dp = new Set[9];

        for (int i = 0; i <= 8; i++)
            dp[i] = new HashSet<>();

        dp[1].add(N);

        for (int i = 2; i <= 8; i++){
            dp[i].add(makeNstr(N, i));

            for (int j = 1; j <= i - 1; j++)
                for(int k : dp[j])
                    for(int h : dp[i - j])
                        calculation(dp, i, k, h);


            if (dp[i].contains(number)) {
                answer = i;
                break;
            }
        }
        return answer;
    }

    private int makeNstr(int N, int i) {
        int num = 0;

        for(int n = 0; n < i; n++)
            num += N * (int)Math.pow(10, n);

        return num;
    }

    private void calculation( Set<Integer>[] dp, int i, int k, int h) {
        dp[i].add(k + h);
        dp[i].add(k - h);
        dp[i].add(k * h);
        if(h != 0)
            dp[i].add(k / h);
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(5,12);
        assertEquals(4, result);
    }

    @Test
    public void solution_2(){
        int result = solution.solution(2,11);
        assertEquals(3, result);
    }

    @Test
    public void solution_3(){
        int result = solution.solution(8,5800);
        assertEquals(8, result);
    }
}

순위

• n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다
• 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다
• 정확하게 순위를 매길 수 있는 선수의 수 구하기

📝 Solution

Key Idea

• 그래프의 정보를 저장할 이차원 배열에 matching[i][j]
• 자기 자신이면(i == j) 0,
• i가 j에게 이겼다면 1,
• i가 j에게 졌다면 -1,
• 알수없는 값은 Integer.MAX_VALUE 로 초기화 합니다
• 그래프를 순회하면서 [i][k] 와 [k][j] 가 둘다 1이면
• i는 j에게 무조건 승리하므로 [i][j] 값을 1로 설정하고
• [j][i] 의 값은 -1로 설정해 줍니다
• 그래서 한 행 또는 열에서 모든 경기결과를 알 수 있을 때 (MAX_VALUE가 하나도 없을 때)
• 선수의 수를 카운트하여 답을 구합니다

    public void graph(int[][] matching, int n) {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (matching[i][k] == 1 && matching[k][j] == 1){
                        matching[i][j] = 1;
                        matching[j][i] = -1;
                    }
    }

💻 Code

Solution.java

class Solution {
    public int solution(int n, int[][] results) {
        int[][] matching = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if(i != j)
                    matching[i][j] = Integer.MAX_VALUE;

        for (int[] result : results) {
            matching[result[0]][result[1]] = 1;
            matching[result[1]][result[0]] = -1;
        }

        graph(matching, n);

        return findCertainPlayer(matching, n);
    }

    public void graph(int[][] matching, int n) {
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (matching[i][k] == 1 && matching[k][j] == 1){
                        matching[i][j] = 1;
                        matching[j][i] = -1;
                    }
    }

    private int findCertainPlayer(int[][] matching, int n) {
        int count = 0;

        for (int i = 1; i <= n; i++) {
            boolean check = true;
            for (int j = 1; j <= n; j++)
                if (matching[i][j] == Integer.MAX_VALUE) {
                    check = false;
                    break;
                }
            if(check)
                count++;
        }

        return count;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(5, new int[][]{{4,3},{4,2},{3,2},{1,2},{2,5}});
        assertEquals(2, result);
    }
}

가장 먼 노드

• 1번 노드로 부터 가장 멀리 떨어진 노드가 몇개인지 구하기

📝 Solution

Key Idea

• ArrayList<>를 이용해 양방향 그래프를 만듭니다
• Queue에 한층씩 노드를 넣고 해당 노드에 연결된 노드들을 반복문을 돌며 임시큐에 넣습니다
• 한층씩 이동하며 한층에 해당하는 임시큐의 개수를 세면 최종적으로 남는 개수가 답이 됩니다

        while (true) {
            Queue<Integer> temp = new LinkedList<>();

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int node : graph.get(cur)) {
                    if (!visited[node]) {
                        temp.add(node);
                        visited[node] = true;
                    }
                }
            }

            if (temp.isEmpty())
                break;
            queue.addAll(temp);
            cnt = temp.size();
        }

💻 Code

Solution.java

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int solution(int n, int[][] edge) {
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

        for(int i  = 0; i <= n; i ++)
            graph.add(i, new ArrayList<>());

        for (int[] vertex : edge) {
            graph.get(vertex[0]).add(vertex[1]);
            graph.get(vertex[1]).add(vertex[0]);
        }

        return bfs(n, graph);
    }

    private int bfs(int n, ArrayList<ArrayList<Integer>> graph) {
        int cnt = 0;
        boolean[] visited = new boolean[n + 1];
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        visited[1] = true;

        while (true) {
            Queue<Integer> temp = new LinkedList<>();

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                for (int node : graph.get(cur)) {
                    if (!visited[node]) {
                        temp.add(node);
                        visited[node] = true;
                    }
                }
            }

            if (temp.isEmpty())
                break;
            queue.addAll(temp);
            cnt = temp.size();
        }

        return cnt;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(6, new int[][]{{3,6},{4,3},{3,2},{1,3},{1,2},{2,4},{5,2}});
        assertEquals(3, result);
    }
}

H-index

• 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 구하기

📝 Solution

Key Idea

• 배열을 내림차순으로 정렬한 후, 인덱스보다 해당 인덱스의 배열값이 크거나 같은 인덱스중 최댓값을 구하면 됩니다

💻 Code

Solution.java

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public int solution(int[] citations) {
        int answer = 0;
        Integer[] array = Arrays.stream(citations).boxed().toArray(Integer[]::new);

        Arrays.sort(array, Collections.reverseOrder());

        for (int i = 0; i < array.length; i++)
            if(array[i] >= i + 1)
                answer = Integer.max(answer, i + 1);

        return answer;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution(new int[]{3, 0, 6, 1, 5});
        assertEquals(3, result);
    }
}

가장 큰 수

• 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수 찾기
• numbers의 길이는 1 이상 100,000 이하입니다
• numbers의 원소는 0 이상 1,000 이하입니다

📝 Solution

Key Idea

• 숫자로 0만 주어지는 배열은 배열의 합을 구해서 0이면 "0"으로 처리되도록 해줍니다
• 원소중 가장 긴 숫자의 길이가 4기 때문에, 원래의 숫자를 반복하여 만들어지는 앞의 4자리 수를 객체에 저장합니다
• 위에서 얻은 숫자를 비교하여 큰 것이 앞으로 가도록 정렬하고,
• 만약에 위에서 얻은 숫자가 같다면 원래의 수가 적은 것으로 정렬해야 가장 큰 수를 얻을 수 있습니다

    public String solution(int[] numbers) {
        ArrayList<Number> list = new ArrayList<>();
        StringBuilder builder = new StringBuilder();

        if(Arrays.stream(numbers).sum() == 0)
            return "0";

        for (int number : numbers)
            list.add(new Number(Integer.toString(number)));

        for (Number number : list)
            number.setChanged();

        list.sort((o1, o2) -> {
            if (o1.changed.equals(o2.changed))
                return Integer.parseInt(o1.original) - Integer.parseInt(o2.original);
            return Integer.parseInt(o2.changed) - Integer.parseInt(o1.changed);
        });

        for(Number number : list)
            builder.append(number.original);

        return builder.toString();
    }

💻 Code

Solution.java

import java.util.ArrayList;
import java.util.Arrays;

class Number {
    String original;
    String changed;

    public Number(String original) {
        this.original = original;
    }

    public void setChanged() {
        StringBuilder builder = new StringBuilder();

        while (builder.toString().length() <= 4)
            builder.append(original);

        changed = builder.substring(0, 4);
    }
}

class Solution {
    public String solution(int[] numbers) {
        ArrayList<Number> list = new ArrayList<>();
        StringBuilder builder = new StringBuilder();

        if(Arrays.stream(numbers).sum() == 0)
            return "0";

        for (int number : numbers)
            list.add(new Number(Integer.toString(number)));

        for (Number number : list)
            number.setChanged();

        list.sort((o1, o2) -> {
            if (o1.changed.equals(o2.changed))
                return Integer.parseInt(o1.original) - Integer.parseInt(o2.original);
            return Integer.parseInt(o2.changed) - Integer.parseInt(o1.changed);
        });

        for(Number number : list)
            builder.append(number.original);

        return builder.toString();
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        String result = solution.solution(new int[]{6,10,2});
        assertEquals("6210", result);
    }

    @Test
    public void solution_2(){
        String result = solution.solution(new int[]{3,30,34,5,9});
        assertEquals("9534330", result);
    }

    @Test
    public void solution_3(){
        String result = solution.solution(new int[]{1, 10, 100, 1000});
        assertEquals("1101001000", result);
    }

    @Test
    public void solution_4(){
        String result = solution.solution(new int[]{9,998});
        assertEquals("9998", result);
    }

    @Test
    public void solution_5(){
        String result = solution.solution(new int[]{30,3021});
        assertEquals("303021", result);
    }
}

K번째수

• 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하기

📝 Solution

Key Idea

• Arrays.copyOfRange 를 이용해 i번째부터 j번째까지의 배열을 구합니다
• Arrays.sort 를 이용해 배열을 오름차순으로 정렬하고 k 번째 인덱스의 값을 구합니다

    private int find(Command command, int[] array) {
        int[] subArray = Arrays.copyOfRange(array, command.i - 1, command.j);

        Arrays.sort(subArray);

        return subArray[command.k - 1];
    }

💻 Code

Solution.java

import java.util.ArrayList;
import java.util.Arrays;

class Command {
    int i;
    int j;
    int k;

    public Command(int i, int j, int k) {
        this.i = i;
        this.j = j;
        this.k = k;
    }
}

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer;
        ArrayList<Command> list = new ArrayList<>();

        for (int[] command : commands)
            list.add(new Command(command[0], command[1], command[2]));

        answer = new int[list.size()];

        for(int i = 0; i < answer.length; i++)
            answer[i] = find(list.get(i), array);

        return answer;
    }

    private int find(Command command, int[] array) {
        int[] subArray = Arrays.copyOfRange(array, command.i - 1, command.j);

        Arrays.sort(subArray);

        return subArray[command.k - 1];
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int[] result = solution.solution(new int[]{1, 5, 2, 6, 3, 7, 4}, new int[][]{{2,5,3},{4,4,1},{1,7,3}});
        assertArrayEquals(new int[]{5,6,3}, result);
    }
}

이중우선순위큐

• I 숫자 큐에 주어진 숫자를 삽입합니다
• D 1 큐에서 최댓값을 삭제합니다
• D -1 큐에서 최솟값을 삭제합니다
• 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 구하기

📝 Solution

Key Idea

• 오름차순으로 정렬이 되는 우선순위큐와 내림차순으로 정렬이 되는 우선순위큐 각각 1개씩을 사용합니다
• 삽입할 때에는 두 곳에 모두 삽입을 해줍니다
• 큐에서 최댓값을 삭제할 때에는 내림차순 우선순위큐에서 제일 앞의 값을 꺼내고 오름차순 큐에서 해당 값을 remove() 해줍니다
• 큐에서 최솟값을 삭제하는 것은 위의 방법의 반대로 진행합니다

PriorityQueue<Integer> increase = new PriorityQueue<>((o1, o2) -> o1 - o2);
PriorityQueue<Integer> decrease = new PriorityQueue<>((o1, o2) -> o2 - o1);

for (String operation : operations) {
    String[] tokens = operation.split(" ");

    switch (tokens[0]) {
        case "I" :
            insert(increase, decrease, tokens[1]);
            break;
        case "D" :
            delete(increase, decrease, tokens[1]);
    }
}

💻 Code

Solution.java

import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> increase = new PriorityQueue<>((o1, o2) -> o1 - o2);
        PriorityQueue<Integer> decrease = new PriorityQueue<>((o1, o2) -> o2 - o1);

        for (String operation : operations) {
            String[] tokens = operation.split(" ");

            switch (tokens[0]) {
                case "I" :
                    insert(increase, decrease, tokens[1]);
                    break;
                case "D" :
                    delete(increase, decrease, tokens[1]);
            }
        }
        return find(increase, decrease);
    }

    private void insert(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease, String num) {
        increase.add(Integer.parseInt(num));
        decrease.add(Integer.parseInt(num));
    }

    private void delete(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease, String num) {
        if (num.equals("1") && !decrease.isEmpty()) {
            int current = decrease.poll();
            increase.remove(current);
        } else if (num.equals("-1") && !increase.isEmpty()) {
            int current = increase.poll();
            decrease.remove(current);
        }
    }

    private int[] find(PriorityQueue<Integer> increase, PriorityQueue<Integer> decrease) {
        int[] answer = new int[2];

        if (increase.isEmpty() || decrease.isEmpty())
            return answer;

        answer[0] = decrease.poll();
        answer[1] = increase.poll();

        return answer;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertArrayEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int[] result = solution.solution(new String[]{"I 16","D 1"});
        assertArrayEquals(new int[]{0,0}, result);
    }

    @Test
    public void solution_2(){
        int[] result = solution.solution(new String[]{"I 7","I 5","I -5","D -1"});
        assertArrayEquals(new int[]{7,5}, result);
    }
}