[백준] 온라인 저지 11399번 : ATM(Java), 그리디 & 삽입 정렬

그리디 문제를 찾아 풀다가, 이전에 삽입 정렬을 사용하여 같은 문제를 풀었던 것을 발견하였다.

 

1. 그리디로 풀이

돈을 출금하는데 시간이 적게 걸리는 사람이 앞에 설 수록, 총 소요시간이 적게 걸리는 것을 알면 금방 풀리는 문제로 코드도 간단하다.

import java.util.*;

public class P11399_ATM_그리디 {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N];
        int answer = 0;

        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }

        // 오름차순 정렬
        Arrays.sort(arr);

        int sum = 0;
        for(int i=0; i<N; i++) {
            sum += arr[i];
            answer += sum;
        }

        System.out.println(answer);
    }
}

 

 

 

 

2. 삽입 정렬로 풀이

Arrays.sort() 대신 삽입 정렬을 사용해 배열을 오름차순으로 정렬한 후, 합 배열을 이용해 정답을 구했다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int arr[] = new int[N];
        int sumArr[] = new int[N];

        for(int i=0; i<N; i++) {
            arr[i] = sc.nextInt();
        }

        // 삽입 정렬 수행
        for(int i=1; i<N; i++) {
            int insertPoint = i;
            int insertValue = arr[i];

            for(int j=i-1; j>=0; j--) {
                // 현재 i의 바로 앞칸부터 0까지 탐색
                if(arr[j] < arr[i]) {
                    insertPoint = j+1; // 자신보다 작은 값 한칸 뒤에 삽입해야 하므로 +1
                    break;
                }

                if(j==0) {
                    // 현재 값이 제일 작은 값일 경우 맨 앞에 삽입
                    insertPoint = 0;
                }
            }

            for(int j=i; j>insertPoint; j--) {
                // 삽입 위치에서 i까지 한칸씩 뒤로 밀기
                arr[j] = arr[j-1];
            }
            arr[insertPoint] = insertValue;
        }

        // 합배열 구하기
        sumArr[0] = arr[0];
        for(int i=1; i<N; i++) {
            sumArr[i] = sumArr[i-1] + arr[i];
        }

        int sum = 0;
        for(int i=0; i<N; i++) {
            sum += sumArr[i];
        }
        System.out.println(sum);
    }
}