백준 2751

2019-02-24

백준 2751문제 수 정렬하기 2

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	37278	11358	7331	34.281%

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

예제 출력 1 복사

처음 이 문제를 봤을 때는 엄청 쉬운문제라고 생각해서 정답 비율이 34%밖에 안되는 것에대해 의문이 들었습니다. 하지만 알고리즘을 짜보니 왜 34%인지 알겠더라구요. 먼저 갯수가 1 ≤ N ≤ 1,000,000 개 주어집니다. 하지만 시간 제한은 2초구요. 2초안에 정렬을 끝내야 되는 문제입니다. 즉 어떤 정렬 방법이 가장 최적화 인지를 테스트하는 문제라고 보시면 됩니다.

처음 제가짠 소스는 이렇습니다.

public class Problem2751 {

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);

		// 몇줄 선택
		int row = s.nextInt();

		ArrayList<Integer> values = new ArrayList<>();

		// 입력 받는 for 문
		for (int i = 0; i < row; i++) {
			values.add(s.nextInt());	
		}

		// 오름차순 정렬 하는 코드
		Ascending ascending = new Ascending();
		Collections.sort(values, ascending);
		
		//출력하기
		for(int i=0; i< row; i++) {
			System.out.println(values.get(i));
		}
		s.close();
	}
}

// 오름 차순 구현
class Ascending implements Comparator<Integer> {

	@Override
	public int compare(Integer o1, Integer o2) {
		return o1.compareTo(o2);
	}
}

입력은 Scanner로 받았고, Collections.sort()를 사용해 정렬을 해주었는데요, 이 문제의 정답으로써는 동일하지만 시간초과가 되어 실패하게 되었습니다.

어떤게 문제인지 살펴보도록 하겠습니다.

시간복잡도

시간복잡도는 문제를 해결하는데 걸리는 시간과 함수 관계를 가르킵니다.

이 문제의 주어진 시간은 2초이기 때문에 2초안에 모든걸 해결해야 합니다.

먼저 입력을 받을 때도 시간복잡도가 있습니다.

입력방식	수행시간(초)
java.util.Scanner	6.068
java.io.BufferedReader	0.934

각 언어별 input method 비교

Scanner는 BufferedReader에 비해 많은 수행시간 필요합니다.

그래서 이 문제에서는 BufferedReader를 사용해야 합니다.

다음은 정렬 방식입니다.

버블정렬,선택정렬,삽입정렬은 시간복잡도가 O(n^2) 을 가지고 있습니다. Collections.sort는 시간복잡도가 O(n*log(n)) 를 가지고 있습니다. 이 복잡도는 퀵 정렬,힙정렬이랑 동일한 속도입니다.

그러므로 Collections.sort를 이용해서 정렬을 해주도록 하겠습니다.

정답

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Problem2751 {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 몇줄 선택
		int row = Integer.parseInt(br.readLine());

		// 배열 선언 
		int[] data = new int[row];
		
		// 입력 받는 for 문
		for (int i = 0; i < row; i++) {
			data[i] = Integer.parseInt(br.readLine());
		}
	
		// 오름차순 Comparator 객체 샐성
		Ascending as = new Ascending();
		// primitive type을 wrapper 클래스로 변경해주는 작업
		List<Integer> datas = Arrays.stream(data).boxed().collect(Collectors.toList());
		// 정렬 
		Collections.sort(datas, as);
	
		//출력하기
		for(int i=0; i< row; i++) {
			System.out.println(datas.get(i));
		}
	
	}

}

//오름 차순 구현
class Ascending implements Comparator<Integer> {
	@Override
	public int compare(Integer o1, Integer o2) {
		// TODO Auto-generated method stub
		return o1.compareTo(o2);
	}
}

입력받는 클래스는 BuffereReader를 사용을 했습니다. 처음에 생성할 배열의 크기를 정하고, 그 배열에 넣어주는 방법을 했습니다. 여기서는 int를 사용했는데 Integer를 하게되면 계속 새로운 객체를 생성하기 때문에 시간초과가 뜰 가능성이 있어서, 한꺼번에 wapper 클래스로 변경해주었습니다.

 Mybatis Mock Framework 