[백준] CLASS2 2751 수 정렬하기 2 - JAVA [자바]

 안녕하세요. 이번에는 백준 2751 수 정렬하기 문제를 풀어보려고 합니다.

 

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

2609번: 최대공약수와 최소공배수

---

Problem

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

사진 1. 문제

---

Solution

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

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[] 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 < arr.length; i++) {
            sb.append(arr[i] + "\n");
        }
        
        System.out.println(sb.toString());
    }
}

 이번 문제는 수 정렬하기 문제이다. 이 문제는 간단하게 Sort기능을 사용하면 쉽게 해결이 가능하다. 하지만 다른 사람들은 어떤 식으로 풀었는지 궁금해서 찾아보니 Counting sort를 이용해서 더 빠르게 푼 방식도 있었다. 

 

Counting Sort 방식

import java.io.*;
 
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        
		int N = Integer.parseInt(br.readLine());
		
        // 절댓값이 1,000,000 이므로 +- 해서 2,000,001 을 넣어준다
		boolean[] arr = new boolean[2000001];
		
		for(int i = 0; i < N; i++) {
			arr[Integer.parseInt(br.readLine()) + 1000000] = true;
		}
		
		for(int i = 0; i < arr.length; i++) {
            if(arr[i]){
                sb.append((i - 1000000)).append('\n');    
            }	
		}
        
        System.out.println(sb);
	}
}

 Sort 기능을 사용하지 않고 boolean으로 처리하는 방법을 배울 수 있었다. 앞으로도 종종 나만의 방식뿐만 아니라 다른 사람의 방식도 공부해 보도록 해야겠다.

---

Performance

1. Sort 방식

사진 2. 실행 결과

 

2. Counting Sort 방식

사진 3. 실행 결과

이렇게 1번 방식보다 2번 방식이 메모리와 시간을 많이 절약하는 모습을 확인 할 수 있다. 

---

Reference

https://st-lab.tistory.com/106