[백준/JAVA] 11399번: ATM

🔺 문제

11399번: ATM

 

🔺 코드

import java.util.*;
import java.io.*;
 
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());
        int[] arr = new int[n];     // 자릿수별 배열
        int[] time = new int[n];    // 합 배열
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < n ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        /*** 🔔 삽입 정렬 🔔 ***/
        for(int i = 1 ; i < n ; i++) {
            int insert_point = i; // 1) 현재 인덱스에 있는 데이터 값 선택
            int insert_value = arr[i];
            
            // 2) 현재 범위에서 삽입 위치 찾기
            for(int j = i - 1 ; j >= 0 ; j--) {
                if(arr[i] > arr[j]) {
                    insert_point = j + 1;
                    break;
                }
                
                if(j == 0) {
                    insert_point = 0;
                }
            }
            
            // 3) 삽입 위치에서 데이터를 한 칸씩 뒤로 밀기 (shift)       
            for(int j = i ; j > insert_point ; j--) {
                arr[j] = arr[j-1];
            }
            // 4) 삽입 위치에 현재 데이터 삽입
            arr[insert_point] = insert_value;
        }
        
        // 합 배열 만들기
        time[0] = arr[0];
        for(int i = 1 ; i < n ; i++) {
            time[i] = time[i-1] + arr[i];
        }
        
        // 합 배열 총합 계산
        int sum = 0;
        for(int i : time) {
            sum += i;
        }
        
        System.out.println(sum);
    }
}

✅ 해결 아이디어
- 삽입 정렬 (시간 복잡도 : O(n²))
- 누적합으로 최소 시간 계산 (= DP)

---

🔺 다른 풀이들

- 풀이1) Arrays.sort() 활용

[백준 알고리즘] 백준 11399번 ATM 자바(Java)

Arrays.sort()를 활용한 풀이

 

 

- 풀이2) 카운팅 정렬 활용

[백준] 11399번 : ATM - JAVA [자바]

카운팅 정렬도 사용하셨다.

---

💬 느낀 점

삽입 정렬... 이해하는 데 시간이 좀 오래 걸렸지만 이해하고 나면 재밌는 것 같다.

다음엔 직접 구현할 수 있었으면 좋겠다!

1회독	2회독	3회독	4회독	5회독
V	6.13	12.21	240219

 

 

( + 6.13 2회독)

삽입 정렬 안 하고 그냥 Arrays.sort() 썼다..

import java.io.*;
import java.util.*;
 
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());
        int[] A = new int[N + 1];
  
        String[] s = br.readLine().split(" ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(s[i]);
        }
        
        Arrays.sort(A);
        
        int[] dp = new int[N + 1];
        dp[1] = A[1];
        
        int total = dp[1];
        for(int i = 2 ;  i <= N ; i++) {
            dp[i] = dp[i-1] + A[i];
            total += dp[i];
        }
        System.out.println(total);
    }
}

 

 

 

( + 12.21 3회독)

메모리와 시간을 더 줄여보았다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);    // 배열 오름차순 
        
        int sum = arr[0];
        for(int i = 1 ; i < N ; i++) {
            arr[i] += arr[i - 1];
            sum += arr[i];
        }
        
        System.out.println(sum);
    }
}
 

 

 

 

(+240219 4회독)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    static int[] arr;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        String[] str = br.readLine().split(" ");
        for(int i = 0 ; i < str.length ; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }        
        Arrays.sort(arr);
        
        int sum = arr[0];        
        for(int i = 1 ; i < N ; i++) {
            arr[i] += arr[i-1];
            sum += arr[i];
        }
        
        System.out.println(sum);
    }
}