[24051] 알고리즘 수업 - 삽입 정렬 1 (JAVA)

# 문제 설명

오늘도 서준이는 삽입 정렬 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 삽입 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 삽입 정렬 의사 코드는 다음과 같다.

insertion_sort(A[1..N]) { # A[1..N]을 오름차순 정렬한다.
    for i <- 2 to N {
        loc = i - 1;
        newItem = A[i];

        # 이 지점에서 A[1..i-1]은 이미 정렬되어 있는 상태
        while (1 <= loc and newItem < A[loc]) {
            A[loc + 1] <- A[loc];
            loc--;
        }
        if (loc + 1 != i) then A[loc + 1] = newItem;
    }
}

---

입력

첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 10,000), 저장 횟수 K(1 ≤ K ≤ N2)가 주어진다.

다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)

---

출력

K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

 

# 정답 코드

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));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); //배열의 크기
        int K = Integer.parseInt(st.nextToken()); //저장 횟수

        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int n = 0; n < N; n++) {
            A[n] = Integer.parseInt(st.nextToken());
        }

        int cnt = 0;

        for (int i = 1; i < A.length; i++) {
            int insertIdx = i;
            int insertValue = A[i];

            //삽입 위치 찾기
            for (int j = i-1; j >= 0; j--) {
                if (A[j] < A[i]) {
                    insertIdx = j+1;
                    break;
                }
                if (j == 0) {
                    insertIdx = j;
                }
            }

            //데이터 삽입
            for (int j = i; j > insertIdx; j--) {
                A[j] = A[j-1];

                cnt++;
                if (cnt == K) {
                    System.out.print(A[j]);
                    return;
                }
            }

            A[insertIdx] = insertValue;

            if (insertIdx != i) {
                cnt++;
                if (cnt == K) {
                    System.out.print(insertValue);
                    return;
                }
            }
        }

        System.out.print("-1");
    }
}

 

데이터를 입력받고 배열 A를 만든다.

저장 횟수를 cnt에 저장한다.

 

바깥 for문은 선택 데이터를 지정한다.

삽입할 위치 insertIndex와 삽입할 값 insertValue를 각각 i와 A[i]로 설정한다.

 

선택 데이터를 삽입할 위치를 찾는다.

j를 i-1부터 0까지 돌면서, 오름차순 정렬이므로 선택 데이터의 값보다 A[j]가 작으면 삽입할 위치를 j+1로 설정하고 반복문을 종료한다.

만약 j가 0이면, 배열의 맨 앞에 선택 데이터를 넣어야 하므로 삽입할 위치를 0으로 설정한다.

 

삽입할 위치에 insertValue를 넣어주기 위해 삽입 위치부터 i까지 shift를 해줘야 한다.

이때 값을 옮길 때마다 cnt를 1 증가한다.

shift 연산이 끝나고 insertIndex에 insertValue를 넣어준다.

이때에도 cnt를 1 증가한다.

 

cnt가 증가할 때마다 현재 cnt가 K와 같으면 옮긴 값을 출력한다.

만약 정렬이 끝나고 cnt가 K보다 작으면 -1을 출력한다.