JAVA_버블정렬 알고리즘_수 정렬하기_백준 1750

자바 알고리즘-  수 정렬 알고리즘

시간 제한	메모리 제한
2 초	128 MB

 

수 정렬하기-백준 1750

 

문제

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

입력

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

출력

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

 

▶ 나의 문제풀이 

수의 개수 N(1 ≤ N ≤ 1,000)로 최대 범위가 매우 작기 때문에 O(n²) 시간 복잡도로 알고리즘을 풀 수 있습니다.

버블 정렬의 시간 복잡도가 O(n²) 이므로 버블 정렬 알고리즘을 이용해 정렬해도 시간 복잡도 안에서 문제를 풀 수 있습니다.

N 입력 받기 
반복문으로 arr[N] 배열 수 입력 받기 

for( i = 1; i < N ; i ++ ){
	for( j =0; j<N-i; j++ ){
    	arr[j]값과 arr[j+1]값 비교
        arr[j+1]값이 더 크 면 두 수 교체
        ( tmp_두 변수 값 교체 알고리즘 ) 
	}
}
arr 배열 출력

 

▶ 나의 코드 

package algorithm.doit;

import java.util.Scanner;

public class 수정렬하기_버블정렬 {

	public static void main(String[] args) {

		System.out.println("원하는 수열의 개수를 적으시오 예) 5");
		Scanner sc = new Scanner(System.in);
		// 들어오고자 하는 수의 개수를 N에 담고 배열의 길이로 활용
		int N = sc.nextInt();

		int[] arr = new int[N];

		// for문을 활용하여 다음으로 입력되는 값을 N개 만큼씩 A배열에 저장 될 수 있도록 함
		for (int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		sc.close();

		// 버블 정렬 시작
		for (int i = 1; i < arr.length; i++) {
			for (int j = 0; j < arr.length - i; j++) {
				if (arr[j] > arr[j + 1]) {
					int tmp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = tmp;
				}
			}
		}

		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
}

버블 정렬 결과

 

 

 

 

<참고>

책: do it 알고리즘 코딩 테스트 자바편

코딩 테스트: https://www.acmicpc.net/

참고 자료: https://lordofkangs.tistory.com/131

Baekjoon Online Judge