백준/10989 수 정렬하기 3

수 정렬하기 3

 

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

5 초 (하단 참고)

8 MB (하단 참고)

203593

47199

35651

23.477%

문제

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

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

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

---

풀이

1. 실패 

-> 수 정렬하기 2에서 썼던코드가 통과할거같아서 시도해보았지만 메모리초과로 실패하였다.

int가 4바이트인 반면에 Integer라는 객체는 20바이트정도라는 사실을 구글링해서 알아냈다.

그래서 시간초과보다는 메모리초과가 발생하는듯하다

 

그렇다면 int[]을 이용해서 Arrays.sort()로 풀어보자.

최악의경우 O(N^2)인 정렬방식

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());
        int[] numberArray = new int[n];

        for (int i = 0; i < n; i++) {
            numberArray[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(numberArray);

        for (int i = 0; i < n; i++) {
            bw.write(numberArray[i] + "\n");
        }


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

최악의경우가 테스트케이스에 안들어있었는지 통과

시간복잡도

O(NlogN ~ N^2)

 

다른풀이

카운팅정렬로 풀기

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

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]

 

 

 

출처,더 자세히보기

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

[백준] 10989번 : 수 정렬하기 3 - JAVA [자바]