글 읽기 - String[] 과 int[]의 정렬속도차이

jsoo0511 5년 전 0

처음 코드가 합격한 코드고 두번째 코드가 시간초과가 나온 코드입니다.

첫번째 코드에선 int형 배열에다가 입력한 숫자들을 넣은후 정렬하고,

두번째 코드에선 String형 배열에다가 입력한 숫자들을 넣은후 정렬하여 문제를 해결합니다.

차이는 이것뿐인데 첫번째 코드는 통과가되고, 두번째 코드는 시간초과가 나옵니다.

두 코드의 차이라고는 int[], String[]밖에 없는데 두 타입의 배열을 Arrays.sort가 정렬하는데 속도차이가 있나요?

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sel=new StringTokenizer(br.readLine()," ");
		int num=Integer.parseInt(sel.nextToken());
		int result=Integer.parseInt(sel.nextToken());
		int[] arr=new int[num];  
		
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		

	for(int i=0;i<num;i++){	
			arr[i]=Integer.parseInt(st.nextToken()); //int형 배열에 숫자들을 받음
			
		}
		br.close();
		Arrays.sort(arr);
		System.out.println(arr[result-1]);

	}

}









import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sel=new StringTokenizer(br.readLine()," ");
		int num=Integer.parseInt(sel.nextToken());
		int result=Integer.parseInt(sel.nextToken());
		String[] arr=new String[num]; 
		
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		

	for(int i=0;i<num;i++){	
			arr[i]=st.nextToken();//String형 배열에 숫자를 담음
			
		}
		br.close();
		Arrays.sort(arr);
		System.out.println(arr[result-1]);

	}

}

yukariko 5년 전 1

비교 기반 정렬에선 정수의 경우 두 수를 연산 한번으로 비교할 수 있지만,

문자열의 경우 최악에 모든 문자에 대해 비교를 하게 됩니다.

정수의 정렬 시간복잡도를 O(NlgN) 이라 한다면

문자열은 문자열의 길이가 더해져 O(NlgNM) 이라 할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

String[] 과 int[]의 정렬속도차이

jsoo0511 5년 전 0

yukariko 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말