[BaekJoon] 2751 수 정렬하기2 (java)

🔗 문제 링크

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

👨🏻‍💻 Arrays.sort를 사용한 코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		
		int[] arr = new int[num];
		for (int i=0; i< num; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(arr);
		
		for (int i=0; i<num; i++) {
			bw.write(arr[i]+"\n");
		}
		
		bw.flush();
		bw.close();

	}

}

👨🏻‍💻 Counting Sort Algorithm를 적용한 코드 1

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		
		int[] arr = new int[2000001];
		int position;
		for (int i=0; i< num; i++) {
			position = Integer.parseInt(br.readLine())+1000000;
			arr[position] = 1;
		}
		for (int i=0; i<2000001; i++) {
			bw.write(String.valueOf((i-1000000)+"\n").repeat(arr[i]));
		}
		bw.flush();
		bw.close();
	}

}

👨🏻‍💻 Counting Sort Algorithm를 적용한 코드 2

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

public class Main {

	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int num = Integer.parseInt(br.readLine());
		
		boolean[] arr = new boolean[2000001];
		int position;
		for (int i=0; i< num; i++) {
			position = Integer.parseInt(br.readLine())+1000000;
			arr[position] = true;
		}
		for (int i=0; i<2000001; i++) {
			if(arr[i]) bw.write(String.valueOf((i-1000000)+"\n"));
		}
		bw.flush();
		bw.close();
	}

}

📝 정리

처음에 문제를 풀 때는 Arrays에서 제공하는 Sort알고리즘을 사용하여 오름차순 정렬을 하였다.
Arrays.sort메서드를 사용해도 별 문제 없이 통과는 하였지만 실행시간과 메모리 시간을 줄여보기 위해 Counting Sort Algorithm을 사용하여 다시 코드를 짜보았더니 실행시간이 35%정도 줄어든 것을 확인할 수 있었다. 하지만 아래 사진의 두번째결과를 보면 배열을 int array를 사용하여 메모리 사용량이 크게 늘어난 것을 확인할 수 있었다.

백준 10989 수 정렬하기와 다르게 수의 중복을 허용하지 않는다고 문제에 제시되어 있어서 int array를 boolean array로 변경을 하여보았다. 그랬더니 메모리 사용량 또한 크게 줄어든 것을 확인할 수 있었다.

아래서부터 Array.sort사용, Couning Sort Algorithm사용(int array), Couning Sort Algorithm사용(boolean array)의 테스트 결과를 보여줍니다.

알고리즘 문제를 푸는데 있어 문제 풀이 여부가 가장 중요하지만 메모리 사용량, 실행시간 또한 중요하다고 생각한다. 이러한 기본 문제부터 메모리 사용량, 실행시간 등을 생각하여 프로그래밍하며 성능 좋은 프로그래밍을 하는 습관을 키워야겠다🔥