018 : ATM 인출 시간 / insertion sort

pointer 배정

찾기

 

두번째부터 시작해서 작은수를 왼쪽에 계속 모으는 것

 

lsq는 standard poll로 작용하고 left area에 삽입할 것을 찾는다

 

*하나라도 작은 걸 찾으면 작은것 - 큰것이 되게 오른쪽 것을 pointer로 잡고 break;

최대한 작은 것을 찾아 들어가는 것이 아닌, 점차 완성되는 그림으로 착각할 수 있지만

왼쪽 2의 구간부터 차례로 쌓여가므로 squeezer poll이 지나간 la에서는 오름차순으로 정렬되어 있다

 

 

 

 

 

 

 

lsq poll에서 삽입할 value를 이미 얻었으므로 지워버려도 된다 

 

 

 

 

 

 

 

 

 

S와 TP의 capacity는 동일하다

1번 2번 .. 5번

1번째까지 합, 2번째까지합.. 5번째까지 합

 

 

 

 

 

 

 

 

 

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        // ISC
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();

        // D2F
        int[] TP = new int[V];
        int[] S = new int[V];
        for (int i = 0; i < V; i++) {
            TP[i] = sc.nextInt();
        }

        // O1
        for (int lsq = 1; lsq < V; lsq++) {

            int pointer = lsq;
            int value = TP[lsq];

            for (int j = lsq-1; j >= 0; j--) {
                if (TP[j] < TP[lsq]) {
                    pointer = j+1;
                    break;
                }
                if (j == 0) {
                    pointer = 0;
                }
            }

            for (int j = lsq; j > pointer; j--) {
                TP[j] = TP[j-1];
            }
            TP[pointer] = value;

        }

        // O2
        S[0] = TP[0];
        for (int i = 1; i < V; i++) {
            S[i] = S[i-1] + TP[i];
        }
        int plate = 0;
        for (int i = 0; i < V; i++) {
            plate += S[i];
        }

        // OEC
        System.out.println(plate);

    }
}