[Java] 1단계. 수 정렬하기 [2750번]

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

 

• 예제 입력1

5
5
2
3
4
1

• 예제 출력1

1
2
3
4
5

---

• 문제 접근
  • 데이터의 수는 최대 1,000개로 시간 복잡도가 O(N^2)여도 문제가 되지 않음
  • 시간 복잡도 O(N^2) ⇒ 선택 정렬, 삽입 정렬, 버블 정렬
• 문제 해결
  • O(N^2) 중에서도 그나마 빠른 삽입 정렬로 구현
  • 0번방은 비교할 것이 없으므로 1번 index부터 시작
  • target 이전의 인덱스가 target보다 값이 크다면, target 위치에 이전 인덱스의 값과 스왑
  • target 이전의 익덱스가 target보다 값이 작다면 그 자리 그대로
• 슈도 코드

N (숫자 개수 저장)
A[] (배열 선언 및 초기화)
for(i = 0 ~ N까지 반복){
	A 배열에 데이터 저장
}

insertion_sort 함수 호출
A배열 출력


insertion_sort (A[]){
	for(int i = 1 ~ N-1까지 반복){
		tmp에 A[i] 저장
		for(int j = i-1 ~ 0까지 반복){
			if(A[j]가 tmp보다 크다면){
				A[j+1] = A[j]
				A[j] = tmp
			} else{
				
			}
		}
	}
}

• 코딩하기

package Step13;

import java.util.Scanner;

public class No1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] A = new int[N];
        for(int i = 0; i < N; i++){
            A[i] = scan.nextInt();
        }
        scan.close();
        insertion_sort(A);
        for (int i : A) {
            System.out.println(i);
        }
    }

    private static void insertion_sort(int[] A) {
        for(int i = 1; i < A.length; i++){
            int tmp = A[i];
            for(int j = i-1; j >= 0; j--){
                if(A[j] > tmp){
                    A[j+1] = A[j];
                    A[j] = tmp;
                }
            }
        }
    }
}