[백준] 11399 ATM

1. 문제 설명

문제 링크

2. 접근 방식

삽입 정렬을 이용하여 문제를 풀어보았다.
정렬된 영역에서 현재 값을 삽입할 위치 선택을 위해 단순 반복문을 사용하는 것보다 이진 탐색을 사용하는 것이 그나마 시간이 빠를 것 같아서, 이진 탐색을 이용했다.
이진 탐색에서 중간 값보다 작았을 시, 클 시 start나 end에 그냥 mid를 더해줘서 무한 Loop에 빠지는 실수를 범했다.
start = mid +1, end = mid -1로 해주어서 start= 0, mid = 1인 경우를 대비해줘야 한다.

3. 코드 분석

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 입력
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> list = new ArrayList<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list.add(Integer.parseInt(st.nextToken()));
        }
        // 2.
        for (int i = 1; i < N; i++) {
           int pos =  binarySearch(list, i);
           int value = list.remove(i);
           list.add(++pos, value);
        }

        int [] sum = new int [N];
        sum[0] = list.get(0);
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i-1] + list.get(i);
        }
        int acc = 0;
        for (int i = 0; i < N; i++) {
            acc += sum[i];
        }

        System.out.println(acc);

    }

    public static int binarySearch(ArrayList<Integer> list, int now_idx) {
        int start = 0;
        int end = now_idx-1;

        while (start <= end){
            int mid = (start+end)/2;

            if(list.get(mid)< list.get(now_idx)){
                start = mid+1;
            }
            else if(list.get(mid) > list.get(now_idx)){
                end = mid-1;
            }
            else if(list.get(mid).equals(list.get(now_idx))){
                return mid;
            }
        }
        return end;
    }
}

4. 성장 하기

배열에서 중간 삽입을 어떻게 할지 잘 몰라서, ArrayList를 썼다. 배열만 이용하는 풀이로 해보고 싶어서, 다른 사람의 풀이를 봤다. 방법은 다음과 같다.

• 0 ~ 현재값 -1의 정렬된 영역 중 현재 값이 들어갈 위치 찾기
• 현재 값이 들어갈 위치 + 1 ~ 현재 값의 위치 내의 영역의 값을 Arr[j] = Arr[j-1]로 한칸씩 땡기기.
  (최초의 값인 Arr[현재값 위치]는 어짜피 지어져도 상관 無 -> 값 옮기기 전에 미리 빼놓기만 하면 된다.)

5. 다른 풀이

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 1. 입력
        int N = Integer.parseInt(br.readLine());
        int [] arr = new int [N];
        int [] sum = new int [N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        // 2. 값 넣기
        for (int i = 1; i < N; i++) {
            int insert_idx = i;
            int insert_value = arr[i];
            // 현재 값이 삽입될 위치 찾기
            for (int j = i-1; j >=0; j--) {
                // 현재 자신보다 값이 작은 위치를 찾았다면, 그 앞에 넣으면 됨.
                if(arr[i] > arr [j]){
                    insert_idx = j+1;
                    break;
                }

                if(j == 0) insert_idx =0;
            }
            // 앞쪽 전부 땡기기
            for (int j = i; j > insert_idx ; j--) {
                arr[j] = arr[j-1];
            }
            arr[insert_idx] = insert_value;
        }
        // 3.누적 합의 합 구하기
        sum[0] = arr[0];
        for (int i = 1; i < N; i++) {
            sum[i] = sum[i-1] + arr[i];
        }

        int acc = 0;
        for (int i = 0; i < N; i++) {
            acc += sum[i];
        }

        System.out.println(acc);
    }
}