백준 2751문제 : 수 정렬하기 2

- 2월 24, 2019

백준 2751

백준 2751문제 수 정렬하기 2

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

문제

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

입력

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

출력

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

예제 입력 1 복사

예제 출력 1 복사


xxxxxxxxxx
1
2
3
4
5

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

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


x
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를 이용해서 정렬을 해주도록 하겠습니다.

정답


xxxxxxxxxx
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 클래스로 변경해주었습니다.

이 블로그 검색

프로그래밍