Softeer - 통근버스 출발 순서 검증하기 - Java

1. 문제

https://softeer.ai/practice/6257

2. 풀이

https://velog.io/@trillionaire/Softeer-%EC%9D%B8%EC%A6%9D%ED%8F%89%EA%B0%804%EC%B0%A8-%EA%B8%B0%EC%B6%9C-%ED%86%B5%EA%B7%BC%EB%B2%84%EC%8A%A4-%EC%B6%9C%EB%B0%9C-%EC%88%9C%EC%84%9C-%EA%B2%80%EC%A6%9D%ED%95%98%EA%B8%B0

부분순열 문제인거같아서 한참 고민했는데..
위와 같은 수학적 해법이 있다니 엄청났다!

2-1. 주의사항

N의 최대가 5,000이기 때문에 정답을 long으로 출력해줘야한다!

3. 코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        long count = 0;
        
        for(int i = 0; i < N; i++) {
            long circle = 0;
            
            for(int j = i + 1; j < N; j++) {
                if(arr[i] < arr[j]) {
                    circle++;
                } else if(arr[i] > arr[j]) {
                    count += circle;
                }
            }
        }
        System.out.println(count);
    }
}