1. 문제

2. 아이디어

• 다음 C 코드는 버블 소트의 swap 을 한 횟수를 출력하는 코드이다.
• 버블 소트에서 SWAP 을 하는 경우, 오른 쪽(더 큰 Index)에서 왼쪽(더 작은 index)으로는 한 번 밖에 옮겨질 수 없다.
• 따라서 정렬 전 index - 정렬 후 index 의 최대값으로 버블 소트에서 swap 한 횟수를 알 수 있다.

3. 슈도 코드

for(i : 0 ~ N){
	if 정렬 전 index - 정렬 후 index > max :
    	max = 정렬 전 index - 정렬 후 index
}
print(max + 1)

4. 코드

import java.util.*;
import java.io.*;

class Main {  
  public static void main(String args[]) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    Node[] node_list =new Node[N];

    for(int i = 0; i < N; i++){
      node_list[i] = new Node(i, Integer.parseInt(br.readLine()) );
    }

    Arrays.sort(node_list);

    int max = 0;
    for(int i = 0; i < N; i++){
      if(max < node_list[i].index - i) max = node_list[i].index - i;
    }

    System.out.println(max+1);
    
  }
}

class Node implements Comparable<Node>{
  int index;
  int value;

  public Node(int index, int value){
    super();
    this.index = index;
    this.value = value;
  }

  @Override
  public int compareTo(Node n2){
    return this.value - n2.value;
  }
}

5. 느낀점 및 배운점

• Comparable 과 Comparator 의 차이점을 숙지
• 배열을 정렬 : Arrrays.sort(배열명) --> O(NlogN)