백준 10431번: 줄세우기 [구현][배열][시뮬레이션] - Java

https://www.acmicpc.net/problem/10431

10431번: 줄세우기

cnt만 구하는 것이기 때문에 굳이 배열을 정렬까지 할 필요는 없음..

내 앞에 있는 애들중에 나보다 큰애들만 count

 

시간복잡도는 O(TC*N^2)

삽입정렬과 동일하다고 보면 된다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		
		Scanner sc = new Scanner(System.in);
		
		int TC = sc.nextInt();
		while(TC>0) {
			TC--;
			int tcno = sc.nextInt();
			
			int result = 0;
			
			//배열넣기
			Integer arr[] = new Integer[20]; 
			for (int i = 0; i < 20; i++) {
				arr[i]=sc.nextInt();
			}
			
			//순서 정렬
			for (int i = 1; i < 20; i++) {
				//현재 순서정해야하는 arr[i]기준으로 앞에있는 애들 키 비교하기
				for (int j = i-1; j >= 0; j--) {
					if(arr[j]>arr[i])
						result++;
				}
			}
			
			System.out.println(tcno+" "+result);
		}
	}

}