11399번 문제 링크

위 문제는 삽입 정렬을 연습하기 위한 문제이다. N의 최대값이 1000 이고, 시간 제한이 1초이기 때문에 시간 복잡도가 O(n^2) 이하인 정렬 알고리즘 아무거나 사용해도 가능하다.

문제 자체는 어려운 문제는 아니였다. 삽입 정렬의 정렬 순서를 생각하며, 개념을 코드로 구현해본다고 생각하면 생각보다 쉽게 문제에 접근이 가능하다.

로직

1. 문제에서 시간의 합의 최솟값을 구하기 위해서는 오름차순으로 정렬할 필요가 있다.
2. 삽입 정렬에 핵심은 삽입할 적절한 index를 찾는 것이다. 이를 찾기 위해서는 제일 앞의 인덱스부터 차례로 크기를 비교해야 하므로, 루프와 조건문을 사용하여 구현하였다.
3. 위치 탐색 후 shift 함수를 통해 적절한 위치부터 현재 위치까지 값들을 한칸씩 이동시켜야 한다.
4. 이 후 적절한 위치에 현재 값을 넣어주면 정렬이 끝나게 된다.

헤깔렸던 로직

처음에 배열의 오름차순 순서(앞 → 뒤)로 값을 이동시키도록 구현하였는데, 이러면 이동 시 값들이 바뀌게 된다. 따라서 현재 위치의 index에 index-1 위치의 값을 이동하여 뒤 → 앞 으로 가는 방향으로 이동시켜줘야 한다.

😒 실패

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

public class Main{
    static int[] arr;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 입력 초기화
        arr = new int[N]; // 시간들
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        // 삽입 정렬
        int value = 0;
        for(int i=1; i < N; i++){
            for(int j=0; j < i; j++){
                if(arr[i] < arr[j]){
                    value = arr[i];
                    shift(j,i);
                    arr[j] = value;
                }
            }
        }
        
        // 시간누적합 구하기
        int sum = 0; // 시간의 합 (pi)
        for(int i=1; i <= N; i++){
            for(int j=0; j < i; j++){
                sum += arr[j];
            }
        }
        
        // 출력
        br.close();
        System.out.println(sum);
    }
    
    static void shift(int start, int end){
    // 아래 범위를 잘못 지정하여 잘못된 결과값이 출력.
        for(int i= start; i < end; i++){ 
            arr[i+1] = arr[i];
        }
    }
}

😀 성공

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

public class Main{
    static int[] arr;
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 입력 초기화
        arr = new int[N]; // 시간들
        for(int i=0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 삽입 정렬
        int value = 0;
        for(int i=1; i < N; i++){
            for(int j=0; j < i; j++){
                if(arr[i] < arr[j]){
                    value = arr[i];
                    shift(j,i);
                    arr[j] = value;
                }
            }
        }

        // 시간누적합 구하기
        int sum = 0; // 시간의 합 (pi)
        for(int i=1; i <= N; i++){
            for(int j=0; j < i; j++){
                sum += arr[j];
            }
        }
        
        // 출력
        br.close();
        System.out.println(sum);
    }
    
    // 이동 함수
    static void shift(int start, int end){
        for(int i= end-1; i >= start; i--){
            arr[i+1] = arr[i];
        }
    }
}