[자바] 백준 2750 - 수 정렬하기 (java)

 문제 : boj2750

---

 

필요 알고리즘 개념

•  정렬
  • 정렬이란 무엇인지와 어떻게 구현할 수 있는지 알아야 풀 수 있다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  기본중의 기본! 오름차순으로 정렬만 하면 되는 문제이다. 물론 자바에서 제공하는 sort 함수로 정렬을 해도 되긴하다. 하지만 그러면 너무 난이도가 쉬우니 여러 정렬 방식을 사용해서 한번 풀어보자. 내 경우엔 이하의 3가지로 풀어봤다. 

 

 

1. 자바에서 제공하는 sort 함수 사용

-> 딱히 설명할게 없다. 그냥 사용만 하면 된다! int[] arr이 아니라, ArrayList<Integer> arr와 같이 자바의 Collection을 사용했다면 'Collections.sort(arr);' 을 해주면 된다.

Arrays.sort(arr);

 

2. 버블 정렬

-> 누구나 정렬을 처음 배울 때 한번쯤 구현해봤을 그 버블정렬이다.

for(int i=0;i<count;i++) {
    for(int j=i+1;j<count;j++) {
        if(intList[i]>intList[j]) {
            temp = intList[i];
            intList[i] = intList[j]; 
            intList[j] = temp;
        }
    }
}

 

3. 카운팅 정렬

-> 정렬이라 하면 보통 가장 빠른 정렬로 퀵정렬이나 병합정렬 등을 뽑는다. 하지만 이 문제처럼 값 자체가 그리 크지 않은 경우라면 카운팅 정렬이 가장 빠르다. 어떤건지 잘 모르겠다면 한번 검색해서 개념을 익혀두는게 좋다. 높은 난이도의 문제로 개념을 확장하기가 참 좋은 녀석이다. 예를들어 플래1티어인 '수열과 쿼리 6' 문제의 경우에도 카운팅 정렬 개념을 응용해서 푼게 메인 아이디어였다.

for (int i = 0; i < n; i++) {
    counting[Integer.parseInt(br.readLine())+1000]++;
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 2001; i++) {
    if (counting[i] == 0) continue;
    sb.append(i-1000).append('\n');
}

 

 

---

 

코드 (버블 정렬) : github

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main{
	
	
	public static void main(String args[]) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));			
		
		int count, num;
		count = Integer.parseInt(br.readLine());
		
		if(count>1000 || count<1)
			return;
		
		int[] intList = new int[count];
		
		for(int i=0;i<count;i++) {
			num = Integer.parseInt(br.readLine());
			intList[i] = num;
		}
		
		
		int temp;
		for(int i=0;i<count;i++) {
			
			for(int j=i+1;j<count;j++) {
				if(intList[i]>intList[j]) {
					temp = intList[i];
					intList[i] = intList[j]; 
					intList[j] = temp;
				}
			}
		}
		
		for(int number:intList)
			bw.write(number + "\n");
		
		bw.flush();
		bw.close();
		br.close();
	}
}

 

 

코드 (자바 sort 함수) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

 

코드 (카운팅 정렬) : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] counting = new int[2001];
        for (int i = 0; i < n; i++) {
            counting[Integer.parseInt(br.readLine())+1000]++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 2001; i++) {
            if (counting[i] == 0) continue;
            sb.append(i-1000).append('\n');
        }
        System.out.print(sb);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}