[백준] 2750번 - 수 정렬하기 (삽입 정렬)

수 정렬하기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

141961

80913

56108

58.216%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

 

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

 

 

---

삽입정렬의 주요 핵심

정수 배열이 있을때,

맨 앞에 1번째 요소는 정렬이 되어 있다고 가정하고 시작한다.

그러므로 2번째 요소부터 삽입 대상으로 설정한다.

정렬이 되어있다고 가정한 앞 요소들(현재는 1번째 요소만 존재) 중 2번째 요소가 삽입될 위치 (2번째 요소 보다 큰 값들 중 위치가 가장 앞쪽에 있는 위치) 를 찾는다.

 

만약, 찾았다면 해당 위치부터 삽입대상의 위치(현재는 2번째) 이전까지의 요소들을 한칸씩 뒤로 이동시킨다.

삽입대상의 값을 삽입될 위치에 넣는다.

 

위에 과정을 정렬이 될때까지 반복한다.

 

내 정답 코드

package Baekjoon.sort;

import java.util.Scanner;

/** 템플릿화 (삽입정렬) **/
/** sort : Insertion Sort **/
public class B2750 {
    public static void main(String[] args) {

        //입력
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        //~입력

        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        int[] result = insertionSort(arr); //솔루션

        //출력
        for (int i = 0; i <  result.length; i++) {
            System.out.println(result[i]);
        }
        //~출력

    }

    public static int[] insertionSort(int[] arr) {

        int index = 1; //이동되는 인덱스, 맨 앞에 요소 하나가 정렬되어있다는 가정하에 시작하므로 1부터

        while (index < arr.length) { //배열 범위내까지

            for (int i = index - 1; i >= 0; --i) { //index가 지정 됬을때마다 돌게되는 범위 (정렬되어 있다는 가정하에 앞 요소들 검사)

                if (arr[i] > arr[index]) { //이동되는 인덱스의 요소(i번째) 보다 큰것의 요소 발견순간, (발견된 순간 바꿔야하는건 확정이다)

                    int temp = arr[index]; //삽입될 요소 미리 저장, 한칸씩 뒤로 밀릴때, 가장먼저 밀려서 값이 사라지기 때문에 저장.

                    int j = i; //한칸씩 밀리는 범위를 구하기 위한 변수, 정렬됨을 가정한 요소들중 한칸 밀림 당하지 않아도 되는 요소가 있기때문에,

                    //큰 요소는 일단 발견됬는데, 앞의 요소들 중 큰 요소들이 더 있을 수 있기 때문에, 더 탐색해야함.
                    for (; j >= 0; --j) { //앞 요소로 전진

                        if (arr[j] < arr[index]) { //요소 중에 작은것이 발견된 경우, 앞 요소들은 j요소보다 다 클것이기 때문에 정지.
                            break;
                        }
                    }

                    //한칸씩 뒤로 보내야하는 요소의 경계 결정
                    if(j < 0) j = 0; //정렬됬다고 가정한 앞 요소들이 모두 arr[index]의 값보다 큰 경우, j는 위 반복문에서 -1이 된 상태로 나올 것이기에
                    else ++j; //정렬됬다고 가정한 앞 요소 중 작은것이 발견 된 경우, 작은 요소위치 + 1 이 밀리여하는 범위이다.


                    //한칸씩 뒤로 보내기
                    for (int z = index-1; z >= j; --z) {
                        arr[z+1] = arr[z];

                    }
                    arr[j] = temp; //기억해뒀던 정렬 가정했던 범위의 바로 다음요소를 삽입되어야 하는 위치에 삽입.
                    break;
                }
            }
            index++; //이동되는 인덱스 증가
        }

        return arr;
    }
}

 

삽입정렬로 풀어보았다.

그런데, 코드의 길이가 너무 길다...

뭔가 변수들의 네이밍도 너무 직관적이지 않고..

변수 직관화와 코드의 길이와 로직을 효율적으로 만드는 것을 더 생각해보자..

 

 

참조 : https://www.youtube.com/watch?v=TyF-UHnoqw4