[정렬] 백준 - 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

-문제해설

단순히 정렬하는 문제이지만 그냥 Arrays.sort 사용하고 출력하면 시간초과가 나온다.
Arrays.sort를 사용하려면 입력값 저장하는 배열을 Integer타입으로 사용해야 되고

출력할 때 StringBuffer나 StringBuilder로 출력값을 만들고 출력해야지 시간초과가 나오지 않는다.

이때 Integer타입으로 하는 이유는 Arrays.sort( Object[] ) 는 시간복잡도가 O(n^2) 까지 되지 않는다고 한다..

추측하는 건데 Arryas.sort() 메서드의 매개변수타입은 Object[] 인걸로 보아서 int형이 들어오면 Integer타입으로 오토박싱되고 정렬이 되는 것 같다. 그래서 시간이 오래걸리는 반면 곧바로 Integer타입으로 하면 오토박싱되는 시간을 줄일 수 있는 것 같다.

 

정렬을 이용하지 않고도 맞은사람 풀이 중에서 효율이 좋은 코드도 첨부했다.
문제에서 주어진 최대 크기까지 배열을 선언하고 입력받은 값을 그 배열의 인덱스에 넣어준다.
예를 들면 5를 입력받으면 a배열 1000005 인덱스에 넣어주고

4를 입력받으면 1000004 인덱스,

3을 입력받으면 1000003 인덱스 ....  이렇게 넣어주고 해당 값은 true로 넣는다.

a[1000005] = true

a[1000004] = true

a[1000003] = true

 

그리고 반복문을 돌면서 if( a[i] = true ) sb.append( a[i] + "\n" );

이런식으로 해주면 정렬을 이용하는 것보다 훨씬 빠르다는 것을 알 수 있었다.

 

이때 인덱스를 1000000으로 하는 이유가 문제에서 

이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

라는 문구가 있었기 때문에 -값이 있을 수 있다. -값이 있으면 배열 인덱스에 들어가지 않기 때문에

+1000000을 해준뒤에 배열에 넣어주고 n의 최대값이 1000000이하이므로 배열의 크기는 1000000+1000000+1인

2000001이 되어야 한다.

 

 

-자바( Arrays.sort() 이용 )

package sort;

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

public class BJ2751 {
	private static int n;
	private static Integer[] arr;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt( br.readLine() );
		arr = new Integer[n];
		for( int i=0; i<n; i++ ) arr[i] = Integer.parseInt( br.readLine() );
		
		Arrays.sort(arr);
		StringBuffer sb = new StringBuffer();
		for( int i=0; i<n; i++ ) sb.append( arr[i]+"\n" );
		System.out.println( sb );
	}
}

 

 

-자바( 배열 인덱스 이용 ) 백준 - miin29na님 코드 참고

package sort;

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

public class BJ2751_1 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt( br.readLine() );
		
		int arr_size = 2_000_001;
		int index = 1_000_000;
		
		boolean[] arr = new boolean[arr_size];
		
		for( int i=0; i<n; i++ ) 
			arr[ Integer.parseInt( br.readLine() ) + index ] = true;
		
		StringBuilder sb = new StringBuilder();
		for( int i=0; i<arr.length; i++ ) 
			if( arr[i] ) sb.append( (i-index)+"\n" );
		
		System.out.println( sb );
	}
}

 

 

-파이썬( 기본 sort함수 사용할 때는 pypy3로 해야지 통과한다.)

n = int(input())
arr = []
for i in range( n ):
    arr.append( int(input()) )

arr.sort()
for i in range( n ):
    print( arr[i] )