[JAVA][Baekjoon] 11399번 ATM 🌟🌟

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

---

📌 접근 방식

삽입 정렬을 사용해 풀어보았습니다.

[알고리즘] 삽입 정렬(Insertion Sort)이란?

 

개념은 이해했는데 어떻게 접근해야할 지 쫌 헷갈렸습니다..!

---

✅ PASS CODE

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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int []arr = new int[N];
        int []result = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        for (int i = 1; i < N; i++) {
            int index = i;
            int num = arr[i];
            for (int j = i-1; j >= 0; j--) {
                if (arr[i] > arr[j]) {
                    index = j+1;
                    break;
                }
                if(j == 0) {
                    index = 0;
                }
            }
            for(int j = i; j > index; j--) {
                arr[j] = arr[j-1];
            }
            arr[index] = num;
        }
        result[0] = arr[0];
        for (int i = 1; i < N; i++) {
            result[i] = result[i-1] + arr[i];
        }
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += result[i];
        }
        System.out.println(sum);
    }
}

⚡️ 코드 설명

1. 배열을 두 부분으로 나눕니다.
   • 왼쪽 부분: 이미 정렬된 영역
   • 오른쪽 부분: 아직 정렬되지 않은 영역
2. 두 번째 요소부터 시작하여 적절한 위치를 찾습니다.
   • 선택된 데이터는 임시 변수에 저장합니다.
   • 왼쪽의 정렬된 부분에서 앞쪽 요소들과 비교하며 삽입할 위치를 찾습니다.
3. 비교는 뒤에서 앞으로 진행됩니다.
   • 선택된 데이터보다 큰 요소를 발견하면, 해당 요소를 한 칸 오른쪽으로 이동합니다.
   • 이 과정은 더 작은 요소를 만나거나 배열의 시작점에 도달할 때까지 반복됩니다.
4. 공간이 확보되면, 선택된 데이터를 삽입합니다.

💡 핵심 포인트

✅ 정렬된 부분을 유지하면서 요소를 삽입하는 방식
✅ 앞쪽 요소들과 비교하며 적절한 위치를 찾아 이동
✅ 안정 정렬(Stable Sort)이며, 데이터가 거의 정렬된 경우 효율적

---

반응형

🫶🏻 느낀점

처음엔 헷갈리고 잘 이해가 안 됐지만, 한 단계씩 원리를 따라가다 보니 생각보다 간단한 코드였어요!
그래도 아직 완벽히 익히진 못한 것 같아서, 복습을 통해 더 확실히 다져봐야겠어요! 🙌