SOFT_통근버스 출발 순서 검증하기_6257

문제링크

느낀점

• 일단 브루트포스는 너무 시간초과가 뻔해서 증가수열같은 알고리즘으로 되려나 고민하다가 못찾았다.
• 그러다가 생각난 풀이가 너무 단순해서 설마 했는데 진짜 됐다.
• 그런데 시간복잡도 말고도 답의 자료형을 꼭 고려해볼 필요가 있다,,

설계 : 30분

• 입력된 수들을 배열에 순서대로 저장한다.
• 앞에서부터 순회하면서(i) nums[i]보다 큰값이 나오면 그 뒤로 nums[i]보다 작은값의 개수를 모두 더해야 한다.
• i를 기준으로 맨뒤부터 i+1까지 역순회하면서 더 작은수를 카운트하고, 더 큰수를 만나면 answer에 더한다.

코드(Java)

• 구현 시간: 10분

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] nums = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(st.nextToken());

        long answer = 0;
        int small;
        for (int i = 0; i < n; i++) {
            small = 0;
            for (int j = n-1; j > i; j--) {
                if (nums[j] < nums[i]) small++;
                else answer += small;
            }
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}