백준 11399번(ATM)[JAVA]

풀이

연습 삼아 삽입 정렬로 푼 코드이다. 실제로 삽입 정렬은 코딩 테스트에서 효율적이지 않다. 선택 정렬도 마찬가지다.
선택 정렬과 삽입 정렬, 버블 정렬은 시간 복잡도가 O(n^2)이기 때문에, 이 문제나 백준 1427(소트인사이드)와 같이 시간 제한이 널널하면 쓸 수는 있지만, 널널하다고 해서 효율적인 정렬 방법은 아니기 때문에 그냥 Arrays.sort()쓰는게 더 낫다.

이 문제는 단순히 입력받은 배열을 오름차순으로 정렬한 후, 합 배열의 총합을 구하면 된다. 1 2 3 4 5 의 배열이 있으면 합배열[0] 은 1, 합배열[1]은 1+2=3, 합배열[2]는 1+2+3=6인 것이다. 풀이는 아래 코드와 같다.

소스 코드

import java.util.*;

public class ATM {
	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 insertIdx = i;
			int insertValue = arr[i];
			
			for (int j = i-1; j >= 0; j--) {
				if (j == 0) {
					insertIdx = 0;
				}
				
				if (arr[j] < arr[i]) {
					insertIdx = j+1;
					break;
				}
			}
			for (int j = i; j > insertIdx; j--) {
				arr[j] = arr[j-1];
			}
			arr[insertIdx] = insertValue;
		}
		sumArr[0] = arr[0];
		for (int i = 1; i < n; i++) {
			sumArr[i] = sumArr[i-1] + arr[i];
		}
		
		int result = 0;
		for (int i = 0; i < n; i++) {
			result = result + sumArr[i];
		}
		System.out.println(result);
		
	}
}

태클 감사합니다.
조언 환영입니다.