[백준알고리즘] 정렬 - 11399번 ATM 문제

https://www.acmicpc.net/problem/11399

11399번: ATM

예전에 운영체제 수업에서 스케쥴링 배울때 이런 개념이 있었던것같다..자세히는 기억이 안나지만

빨리 끝나는 프로세스부터 처리하면 전체 처리 시간이 줄어드는 개념이었던것 같다

돈을 인출하는데 시간이 적게 걸리는 사람의 순서부터 배치해야 최적의 결과가 나오겠다

예제 입력에 있는 각 처리시간은 3 1 4 3 2이고 이를 작은수 순으로 정렬하도록 하고 (= 오름차순, 그러면 1 2 3 3 4)

각 자리마다 앞에서부터의 누적 합을 모두 더해주면 되겠다

정렬 알고리즘은 이것저것 배웠지만 어떤 방식을 사용해야 될지 모르겠다..

앞에서부터 두 수끼리를 비교하면서 더 큰 수를 뒤로 보내는 과정을 n번 반복하는 방식을 해보겠다..이게 선택정렬이던가->버블정렬이었음

선택정렬로 고고

마지막에 기다린 시간의 합계를 최대한 간단히 구하도록 하고자 나름 노력했다

이전에 합한 값을 재활용해 연산하도록 temp변수를 사용해서 더해지도록 했다

 

풀이코드

package baekjoonWeek2;

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

public class ATM {  //백준 11399번 ATM 문제
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());   //사람의 수 입력
        StringTokenizer st = new StringTokenizer(br.readLine());    //각 사람마다 걸리는 시간 입력
        int[] seq = new int[N];
        for (int i = 0; i < N; i++) {
            seq[i] = Integer.parseInt(st.nextToken());
        }
        //정렬부터
        int max = 0;
        int maxIndex = 0;
        int temp = 0;
        for (int i = 0; i < N; i++) {
            max = 0;
            for (int j = 0; j < N - i; j++) {
                if (max < seq[j]) {
                    max = seq[j];   //가장 큰 값 찾기
                    maxIndex = j;   //가장 큰 값 위치
                }
            }
            //교환
            temp = seq[N-i-1];
            seq[N-i-1] = max;
            seq[maxIndex] = temp;

        }
        int waitSum = 0;    //기다린 시간 합계
        temp = 0;
        for (int i = 0; i < N; i++) {
            waitSum += (seq[i] + temp); 
            temp += seq[i]; //seq[i]의 누적값 저장
        }
        bw.write(Integer.toString(waitSum));
        bw.flush();
        bw.close();
    }
}