간단하게 설명하면, 삽입정렬은 0번지부터 시작해서 앞에 있는 것들이 모두 정렬되었다!
라고 생각하고 1번지부터 앞의 정렬 사이에 쏙쏙 끼워넣는 것이다!
<예시>
| 3 | 1 | 4 | 3 | 2 |
|
3은 이미 정렬된 것으로 보고, 1을 뽑아낸다.
1은 3 보다 작으므로 3 앞에 가야 한다. |
||||
| 3 | 4 | 3 | 2 | |
| 1 | 3 | 4 | 3 | 2 |
|
같은 방식으로 4도 뽑아낸 다음,
앞에 정렬된 1, 3 사이에 넣어야 한다. 4는 3보다 크므로, 3 뒤에 온다. 그 다음 3은 4보다 작으므로 4 앞에 넣어준다. |
||||
| 1 | 3 | 4 | 2 | |
| 1 | 3 | 3 | 4 | 2 |
| 2는 3보다 작으므로 3 앞에 넣어준다. | ||||
| 1 | 3 | 3 | 4 | |
| 1 | 2 | 3 | 3 | 4 |
관련 문제 - 백준 11399번 ATM
https://www.acmicpc.net/problem/11399
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] line = br.readLine().trim().split(" ");
//배열입력
int[] atm = new int[n];
for(int i=0; i<n; i++) {
atm[i] = Integer.parseInt(line[i]);
}
//삽입정렬
for(int i=1; i<n; i++) {
int index = i;
int value = atm[i];
//만약 앞에 value보다 큰 수가 있다면,
//큰 수가 있는 위치가 바로 삽입할 위치!
for(int j=i-1; j>=0; j--) {
if(atm[i]<atm[j]) {
index = j;
}
}
//삽입할 위치부터 한칸씩 뒤로 밀기
for(int j=i; j>index; j--) {
atm[j] = atm[j-1];
}
atm[index] = value;
}
//걸리는 시간 합 구하기
int[] time = new int[n];
for(int i=0; i<n; i++) {
for(int j=0; j<=i; j++) {
time[i] += atm[j];
}
}
//총합
int sum = 0;
for(int x : time) {
sum += x;
}
System.out.println(sum);
}
}
이것저것 공부하기