[백준알고리즘-JAVA]2750번 풀이(수 정렬하기) - 초보도 이해하는 풀이

안녕하세요

인포돈입니다.

백준 알고리즘 2750번 풀이입니다. 


* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2750 (수 정렬하기)

 

문제

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

입력

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

출력

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

입력 예시

5
5
2
3
4
1

출력 예시

1
2
3
4
5

성공코드

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

public class Main {
	
	public static void main(String args[]) throws IOException{
	   	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	   	 
	   	 	int num = Integer.parseInt(br.readLine());
	   	 	int[] num_arr = new int[num];
	   	 	
	   	 	for(int i = 0 ; i < num_arr.length; i ++) {
	   	 		num_arr[i] = Integer.parseInt(br.readLine());
	   	 	}
	   	 	
	   	 	int temp = 0;
	   	 	
	   	 	for(int i = 0 ; i < num_arr.length ; i ++) {
	   	 	for(int j = i+1 ; j < num_arr.length; j++) {
	   	 		if(num_arr[i] > num_arr[j]) {
	   	 			temp = num_arr[i];
	   	 			num_arr[i] = num_arr[j];
	   	 			num_arr[j] = temp;
	   	 		}
	   	 	}
	   	 	}
	   	 	
	   	 	for(int i : num_arr)
	   	 		System.out.println(i);

	   	 	}
		}

수 정렬하기 알고리즘은 사실 이미 널리 알려져 있는 간단한 정렬 방법입니다. 아마 프로그래밍을 배우면서 오름차순으로 숫자를 정렬하는 법은 해당 방법으로 가장 먼저 배울 것입니다.

 

해당 알고리즘은 쉬우니 바로바로 넘어가 봅시다!

---

알고리즘 흐름도

입력받기 -> 받은 입력을 옮겨 담을 변수 생성 -> 반복문 2개를 반복하며 정렬하기 -> 출력하기

---

 STEP1 받은 입력 타입 변경해주기

일단 입력을 받으면 String 타입으로 반환이 되기 때문에 순서를 파악하기 쉽게 int형으로 바꿔주는 작업을 해야 합니다

for(int i = 0 ; i < num_arr.length; i ++) {
	   	 		num_arr[i] = Integer.parseInt(br.readLine());
	   	 	}

해당 코드는 해당 숫자를 하나씩 입력할 때마다 int배열에 하나씩 넣어주는 작업입니다! 해당 코드는 별로 어렵지 않은 코드입니다!

---

STEP2 반복문을 어떻게 반복시킬지 고심하기

for(int i = 0 ; i < num_arr.length ; i ++) {
	   	 	for(int j = i+1 ; j < num_arr.length; j++) {
            }
	   	 	}
	   	 	

이번 STEP부터는 예시를 들고 설명해 드리겠습니다!

5 2 3 4 1

해당 코드를 정렬하기 위해서는 아래와 같이 이동이 되어야 합니다.

5 2 3 4 1

i j          

i = 5 / j = 2

이런 식으로 해당 인덱스의 값들을 저장하여 비교를 합니다.

그렇게 된다면 i보다 j는 항상 1보다 큰 값을 가지고 반복해야 됩니다. 이에 따라 for문을 해당 코드처럼 짤 수 있습니다

---

STEP 3 어떠한 방식으로 정렬할 것인가

5 2 3 4 1

i j       

해당과 같이 i가 첫 번째 인덱스를 가리키고 있고, j가 i+1번째 인덱스를 가지고 있다고 하자(앞선 for문처럼)

만약에 i가 크다면

--------------------------------

i의 값을 임의 이 변수에 넣어줍니다.

j의 값을 i에 넣어줍니다.

임의의 변수의 값을 j에 넣어줍니다.

---------------------------------

여기서 이 3줄의 순서가 가장 중요합니다. 코드는 상위부터 시작됨으로 꼭 해당 순서를 지켜주셔야 한다는 것입니다.

for(int i = 0 ; i < num_arr.length ; i ++) {
	   	 	for(int j = i+1 ; j < num_arr.length; j++) {
	   	 		if(num_arr[i] > num_arr[j]) {
	   	 			temp = num_arr[i];
	   	 			num_arr[i] = num_arr[j];
	   	 			num_arr[j] = temp;
	   	 		}
	   	 	}
	   	 	}

해당 순서처럼 값을 넣어준다면 끝!!

 

해당 알고리즘을 쉽게 해결할 수 있음을 알 수 있습니다!