백준/2751 수 정렬하기 2

수 정렬하기 2 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

226499

65082

45252

30.451%

문제

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

입력

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

출력

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

예제 입력 1 복사

5
5
4
3
2
1

예제 출력 1 복사

1
2
3
4
5

 

---

풀이

오름차순으로 정렬하는 간단한 문제같지만 주어지는 수의 개수의 최대값이 백만이나 된다.

O(n^2)의 시간복잡도를 가지는 코드라면 연산횟수가 2억이 넘어서 시간제한을 통과하지못할것이다 (1초에 연산 1억번)

 

최악의경우 시간복잡도가 O(n^2)인 Arrays.sort()를 사용시 실패할수도 있다.

그러므로 최선,최악 둘다 O(NlogN)인 List.sort()를 사용한다.

 

+
빠른입출력인 BufferedReader,BufferedWriter도 사용해주자.

 

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int n = Integer.parseInt(br.readLine());
        List<Integer> numberList = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            numberList.add(Integer.parseInt(br.readLine()));
        }

        numberList.sort(Comparator.naturalOrder());

        for (int i = 0; i < n; i++) {
            bw.write(numberList.get(i) + "\n");
        }

        bw.flush();
        bw.close();
    }
}

시간복잡도

인덱스를 사용하지않고 맨뒤에 넣는 List.add()는 시간복잡도 O(1)

List.sort는 O(NlogN)

ArrayList의 조회는 O(1)이므로

 

총 시간복잡도 O(NlogN)?

 

 

다른 사람 풀이

1. 여러가지 정렬사용해보기

https://st-lab.tistory.com/106

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]