[코딩테스트] 백준 11399

백준 11399

백준 11399 문제

해당 문제는 인출 필요 시간이 짧은 사람순(오름차순)으로 정렬하여 총 인출 소요 시간을 최소로 줄여야한다.

삽입 정렬로 오름차순 정렬한 후 합 배열의 모든 값을 더하여, 총 인출 소요 시간을 구하면 된다.

import java.util.*;

public class Boj11399 {

    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 배열 저장
            arr[i] = sc.nextInt();
        }

        for (int i = 1; i < n; i++) { // n만큼 반복
            int insertPoint = i; // 삽입 위치
            int insertValue = arr[i]; // 현재 데이터

            // 현재 범위에서 십입 위치 찾기
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    insertPoint = j + 1;
                    break;
                }
                if (j == 0) {
                    insertPoint = 0;
                }
            }

            // 삽입을 위해 삽입 위치에서 i까지 데이터를 한 킨씩 뒤로 밀기
            for (int j = i; j > insertPoint; j--) {
                arr[j] = arr[j - 1];
            }
            arr[insertPoint] = insertValue; // 삽입 위치에 현재 데이터 넣기
        }

        // 합 배열 sumArr 만들기
        sumArr[0] = arr[0];
        for (int i = 1; i < n; i++) {
            sumArr[i] = sumArr[i - 1] + arr[i];
        }

        int sum = 0;

        // sumArr 배열의 각 데이터 값을 모두 합해 총 걸리는 시간 구하기
        for (int i = 0; i < n; i++) {
            sum = sum + sumArr[i];
        }

        System.out.println(sum);
    }
}

풀이

1. 사람의 수 n을 입력 받는다.
2. 걸리는 시간을 저장하는 arr 배열을 선언한다.
3. 각 사람이 인출이 완료하는 데 필요한 시간을 저장하는 sumArr 합 배열을 선언한다.
4. arr 배열에 값을 할당한다.
5. 1부터 n만큼 반복을 한다.
6. 현재 데이터가 삽인될 위치인 insertPoint를 선언하고 우선 현재 데이터의 인덱스로 초기화해준다.
7. 현재 데이터를 저장하고 있을 insertValue를 선안하고 현재 데이터를 저장한다.
8. i - 1부터 0까지 내려가면서 현재 데이터보다 작은 값의 위치(삽입 위치)를 찾아 insertPoint를 갱신한다.
9. insertPoint부터 현재 데이터 위치까지 데이터를 오른쪽으로 한 칸씩 이동시킨다.
10. insertPoint에 insertValue를 저장한다.
11. 위 방법을 배열 끝까지 수행한다.
12. 배열이 오름차순으로 정렬되었기 때문에 sumArr[0]에 arr[0] 데이터를 저장해주고, 1부터 반복하며 sumArr 합 배열을 만들어준다.
13. sumArr의 모든 데이터를 sum 변수에 모두 더해서 총 소요 시간을 구하여 출력한다.