[알고리즘] 1-3. 삽입 정렬 #

1. 삽입 정렬

: 이미 정렬된 데이터 범위에 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬

-> 시간복잡도는 O(n^2)으로 느리지만, 구현하기 쉽다.

 

(1) 구현 과정

-> 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입

1. 현재 index에 있는 데이터 값 선택
2. 현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색
3. 삽입 위치부터 index에 있는 위치까지 shift 연산 수행
4. 삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행
5. 전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때까지 반복

-> 삽입 위치를 찾는 탐색 과정에서 정렬되었을 경우 이진 탐색을 사용해 시간 복잡도를 단축 시킬 수 있다.

 

---

문제 18. ATM 인출 시간 계산하기

인하은행에는 ATM이 1 대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서 있다. 사람은 1 번에서 N번까지 번호가 매겨져 있으며，사람이 돈을 인출하는 데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서 돈을 인출하는 데 필요한 시간의 합이 달라진다. 예를 들어 총 5명이
있고，P1= 3, P2 = 1,P3 = 4, P4 = 3, P5 = 2일 때를 생각해 보자. [1，2, 3, 4, 5] 순서로 줄을 선다면

 1번 사람은 3분 만에 돈을뽑을수 있다.

 2번 사람은 1 번 사람이 돈을뽑을 때까지 기다려야하므로 3 + 1=4 분이 걸린다.

 3번 사람은 1 번，2번 사람이 돈을 뽑을 때까지 기다려야 하므로 총 3 + 1 + 4 = 8분이 걸린다.

 4번 사람은3 + 1 + 4 + 3 = 11분

 5번 사람은 3 + 1 +4 + 3 + 2 = 13분이 걸린다.

 

즉，각사람이 돈을 인출하는 데 필요한 시간의 합은 3 + 4 + 8 + 11+13 = 39분이다.

[2, 5,1,4, 3] 순서로 줄을 선다면

 2번은 1분,

 5번은 1 + 2 = 3분,

 1번은 1 + 2+ 3 = 6분,

 4번은 1 + 2 + 3 + 3 = 9분,

 3번은 1 +2 + 3 + 3 + 4 = 13분이 걸리므로

 각 사람이 돈을인출하는 데 필요한시간의 합은 1+3 + 6 + 9 + 13 = 32분이다.

 

이 순서보다 모든 사람이 돈을 인출하는 데 필요한 시간이 짧을 수는 없다.

 

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는 데 걸리는 시간 Pi가 주어졌을 때 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력
1번째 줄에 사람의 수 N(1 < N < 1,000)

2번째 줄에 각 사람이 돈을 인출하는 데 걸리는 시간 Pi(1 < Pi < 1,000)가주어진다.

 

출력
1 번째 줄에 각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값을 출력한다.

예제 입력 1

5 //데이터 개수 32
3 14 3 2

예제 출력 1

32

---

1단계. 문제 분석하기

-> ATM 앞에서 모든 사람이 가장 빠른 시간에 인출하는 방법 : 그리디 알고리즘

-> 인출 시간이 가장 적게 걸리는 사람이 먼저 인출할 수 있도록 순서를 정하는 알고리즘

-> 인출 시간을 기준으로 값을 정렬 : 삽입 정렬

 

2단계. 손으로 풀어보기

1. 삽입 정렬을 잉요해 인출 시간 Pi를 기준으로 데이터를 오름차순 정렬
2. 정렬된 데이터를 바탕으로 모든 사람이 돈을 인출하는 데 필요한 최솟값 도출
   -> 인출에 필요한 시간 = 앞 사람들의 인출 시간의 합 + 자신의 인출 시간 : 합 배열 이용

 

3단계. 슈도코드 작성하기

N（사람 수）
A（자릿수별로 구분해 저장한 배열）
S（A 합 배열: 각 사람이 인출을 완료하는 데 필요한 시간을 저장하기）
for（N만큼 반복하기） {
A 배열 저장하기
}
for（i: N만큼 반복하기） {
    for（j: i - 1 ~ 0까지 뒤에서부터 반복하기） {
    현재 범위에서 삽입 위치 찾기
    }
    for（j: i ~ insert point + 1까지 뒤에서부터 반복하기） {
    삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
    }
    삽입 위치에 현재 데이터 삽입하기
  }
for（i: N만큼 반복하기） {
    A 배열을 통한 합 배열 S 만들기
  }
    
S 배열의 각 데이터 값을 모두 합해 결과 출력하기

 

package sorting.ch04;
//#
import java.util.Scanner;

public class sorting_q18 {
	public int solution(int n, int[] arr) {
		int[] sum = new int[n];
		// sum[i] = sum[i-1]+answer[i];
		
		//삽입 정렬은 두 번째 부터 시작
		for(int i=1;i<n;i++) {
			int index = i;
			int value=arr[i];
			for(int j=i-1; j>=0;j--) {
				//i번째 전부터 처음까지
				if(arr[j]<arr[i]) {
					index=j+1;
					break;
				}
				if(j==0) index=0;
				//index가 1부터 시작했으므로, 예외처리로 첫 번째는 0으로 설정
			}
			for(int j=i; j>index;j--) arr[j]=arr[j-1];
			
			arr[index]=value;
		}
		sum[0]=arr[0];
		//첫 번째 합배열은 반드시 한 개 뿐이므로
		for(int i=1;i<n;i++) sum[i]=sum[i-1]+arr[i];
		
		int answer=0;
		for(int i=0;i<n;i++) answer=answer+sum[i];

		return answer;
	}

	public static void main(String[] args) {
		sorting_q18 T = new sorting_q18();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		System.out.println(T.solution(n, arr));

	}
}

 

 

 

for（i: N만큼 반복하기） {
    for（j: i - 1 ~ 0까지 뒤에서부터 반복하기） {
    현재 범위에서 삽입 위치 찾기
    }
    for（j: i ~ insert point + 1까지 뒤에서부터 반복하기） {
    삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
    }
    삽입 위치에 현재 데이터 삽입하기
  }
for（i: N만큼 반복하기） {
    A 배열을 통한 합 배열 S 만들기
  }
    
S 배열의 각 데이터 값을 모두 합해 결과 출력하기

for (int i = 1; i < n; i++) {
    int index = i;
    int value = arr[i];

    for (int j = i - 1; j >= 0; j--) {
        if (arr[i] > arr[j]) {
            // 최솟값을 선택해, 해당 위치에 삽입
            index = j + 1;
            break;
        }
        if (j == 0)
            index = 0;
    }
    for (int j = i; j > index; j--) {
        arr[j] = arr[j - 1];
    }
    arr[index] = value;
}

sum[0] = arr[0];
for (int i = 1; i < n; i++)
    sum[i] = sum[i - 1] + arr[i];
for (int x : sum)
    answer += x;

return answer;