[인프런] 06-03 삽입 정렬

📖  문제

---

• 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
• 두 번째 줄에 N개의 자연수가 공백을 사이에 두고 입력됩니다. 각 자연수는 정수형 범위 안에 있습니다.
  • N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.
  • 정렬하는 방법은 삽입정렬입니다.

출력 예시

 

⚠️  주의사항

---

• 삽입 정렬을 사용합니다.
• 오름차순입니다.

 

✍️  이해

---

/**
 * 1. N과 N개의 숫자로 이루어진 배열 arr 입력
 * 2. 삽입 정렬이므로 temp에 arr[i] 저장
 * 3. 이중 for문에서 2번째 for문은 오른쪽에서 왼쪽으로 오게 해야 함
 *  3-1. arr[j] > temp -> arr[j+1] = arr[j] 한 칸씩 이동
 *  3-2. else break
 * 4. arr[j+1] = temp
 * 5. return arr;
 */

 

✏️  풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public int[] solution(int N, int[] arr){
        for (int i = 1; i < N; i++) {
            int temp = arr[i], j;
            // j가 두 번째 for문 밖에 있기 떄문에 선언을 해줘야 한다.

            for (j = i - 1; j >= 0; j--) {
                if (arr[j] > temp) arr[j + 1] = arr[j]; // 한 칸씩 왼쪽으로 이동
                else break; // 더 이상 비교 할 필요가 없음
            }
            arr[j + 1] = temp;
        }
        return arr;
    }

    public static void main(String[] args) throws IOException {

        Main T = new Main();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = 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 : T.solution(N, arr)) System.out.print(i + " ");
    }
}

---

2022.02.03 - [Java/이론 및 사용방법] - 삽입정렬