백준 2750번 수 정렬하기(JAVA)

 📌문제   

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

입력

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

출력

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

예제 입력 1

5
5
2
3
4
1

예제 출력 1

1
2
3
4
5

 

 📌해설&답   

🔹풀이1 : 쉬운 방법 - sort 이용

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] num = new int[n];
        for(int i= 0; i<n; i++) {
            num[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(num);
        
        for(int ans : num) {
            System.out.println(ans);
        }
    }
}

 

🔹풀이2 : 속도가 빠른 방법 - 뇌피셜로 알고리즘 짜보기..

* IDEA)
  1. -1000 <= X <= 1000 범위의 숫자가 중복없이 주어지므로, 이 숫자를 다 수용할 수 있는 2001 크기의 boolean 배열을 만든다. (이 배열의 이름을 'num'이라 하자.)
  2. 각 숫자(X)와 일치하는 index 번호에 값을 true로 변경하고, true인 값만 index 순서대로 출력해주면 정렬된 값이 나온다.
    ex) X=256 → num[256] = true 대입. X=4 - → num[4]=true 대입, 이를 index 순서로 출력하면 4, 256이 출력됨
  3. 음수는 일치하는 index가 없으므로, 가공한 후 대입한다. [-1000,-1]을 1001~2000번 index에 넣어줄 것이다.
    가공 방법은 i = |X|+1000
    ex) x=-1 → i =1001번 index에 대입, x=-1000 → i = 2000번 index에 대입

 

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); //입력받을 숫자의 개수 
        boolean[] num = new boolean[2001]; //-1000 <= X <= 1000 : 2001칸짜리 배열 생성 
        Arrays.fill(num,false); //배열의 기본값은 false, 입력값과 일치하는 index의 값만 true로 변경할 것임  
        int temp = 10000;
        
        //숫자 정렬하기 
        for(int i = 0; i < n; i++) {
            temp = Integer.parseInt(br.readLine()); //입력받은 수 
            if(temp < 0) { //입력받은 숫자가 음수일 때 |X|+1000번에 저장,
                temp = Math.abs(temp) + 1000; //-1이면 1001, -2면 1002 ...-1000이면 2000번에 저장
                num[temp] = true;
            }
            else num[temp] = true; //입력받은 숫자가 양수일 때, 숫자와 일치하는 index의 값 true로 변경 
        }

		//출력하기 (num배열에서 값이 true인 것만 출력하면 된다.) 
        StringBuilder sb = new StringBuilder();
        for(int i = num.length-1; i >= 1001; i--) { //음수먼저 출력 
            if(num[i]) sb.append((-1)*(i-1000)+"\n"); //i=|X|+1000 -> X = -1*(i-1000)
        }

        for(int i = 0; i <= 1000; i++) { //양수 및 0 출력(index 그대로)
            if(num[i]) sb.append(i+"\n");
        }
        System.out.println(sb);
    }
    
}

 

📌코멘트

방법 3 -  정렬 알고리즘..(버블, 선택 등...) 

이게 더 알고리즘 공부에 도움이 되니까 한번 짜보자..

 

 

 

끝까지 읽어주셔서 감사합니다 :)

Have a good day🐱

 

---

📢

1. 개발자 준비생이 공부한 내용을 정리한 글입니다. 내용에 오류가 있을 수 있습니다.
2. 위와 같은 이유로 내용에 대한 지적과 조언은 감사하게 받습니다.
3. 이 글의 내용은 계속 공부함으로써 언제든지 추가/수정 될 수 있습니다.