[백준] 11399번 ATM - 삽입정렬 / 오름차순 정렬 / 계산

문제

 

 

로직

사람의 수 입력받기

필요한 시간 배열 선언 및 크기 지정

반복문
- 필요한 시간 입력 받기 & 배열에 저장

while 반복문 

- 삽입 정렬한 부분의 젤 큰 값(오름차순 정렬되어있으므로 가장 인덱스가 큰 값)이 선택한 데이터보다 클 때

   - 1. for 반복문 

        -> 삽입 정렬한 부분에서 선택한 데이터이 삽입될 인덱스 찾음(point)

        -> 반복문 종료

 

   - 선택한 데이터값 저장(select)

 

   - 2. for 반복문

      - 선택한 데이터가 삽입할 부분의 앞의 값들을 앞으로 이동

 

   - 선택한 데이터 삽입

 

- index값 증가

 

위 설명의 예시

3. for 반복문
- 합 계산

-> 합 출력

 

 

My Code

import java.io.*;
import java.util.StringTokenizer;

public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(bf.readLine());
int [] numArray = new int[N];

StringTokenizer st = new StringTokenizer(bf.readLine());

for (int i = 0; i<N; i++)
{
numArray[i] = Integer.parseInt(st.nextToken());
}

int index = 1;
while(index < N){
if (numArray[index-1]>numArray[index]){
int point = 0;
int select = 0;
for (int i = 0; i < index; i++){
if(numArray[i] > numArray[index]){
point = i;
break;
}
}
select = numArray[index];
for (int j = index; j > point; j--){
numArray[j] = numArray[j-1];
}
numArray[point] = select;
}
index++;
}
int sum = 0;
int result = 0;
for (int i = 0; i<N; i++)
{
sum += numArray[i];
result += sum;
}
System.out.println(result);
}
}

 

 

문제의 핵심 및 알게된 점

필요한 시간이 작은 값부터 계산하면 최솟값이 나온다.

따라서 오름차순 정렬 후 가장 작은 값부터 합하면 최소의 결과를 구할 수 있다.

이번 문제에서는 오름차순 정렬을 삽입정렬을 통해서 구현했다.

 

 

 

참고 강의_인프런의 Do it! 알고리즘 코딩테스트 with JAVA