백준 10989 / 수 정렬하기 3

1. int[] 배열 이용

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

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int[] list = new int[10000];
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {
			int val=Integer.parseInt(br.readLine());
			list[val-1]++;
		}
		for(int i=0;i<10000;i++) {
			while(list[i]>0) {
				sb.append((i+1)+"\n");
				list[i]--;
			}
		}
		System.out.println(sb.toString());
	}
}

 최대 배열의 수가 10000000이고 숫자는 10000이하 인 자연수이기 때문에 int에서 모두 해결이 가능하다.

오름차순 정렬이기 때문에, sort를 이용하지 않고 int[]로 해결이 가능하다.

 

 많은 문자열을 줄바꿈으로 저장할 때 BufferedWriter의 성능이 StringBuilder보다 좋다. (메모리 효율)

sb.append(i+"\n") 보다는 sb.append(i).append("\n")의 성능이 더 좋다. 

 

 

2. List<Integer> 이용(메모리초과)

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

public class Main {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		List<Integer> list = new ArrayList<>();
		
		StringBuilder sb = new StringBuilder();
		for(int i=0;i<num;i++) {
			list.add(Integer.parseInt(br.readLine()));
		}
		Collections.sort(list);
		for(int val : list) {
			sb.append(val+"\n");
		}
		System.out.println(sb.toString());
	}
}

List<Integer>를 만들어 배열에 추가하였더니 메모리초과가 발생하였다.

List<Integer>를 이용하는 것보다 int[]를 이용할 수있으면 훨씬 메모리를 절약할 수 있다.