백준/2750 수 정렬하기

문제

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

입력

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

출력

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

예제 입력 1 복사

5
5
2
3
4
1

예제 출력 1 복사

1
2
3
4
5

---

풀이

중복없는 숫자배열을 받은 후 정렬메소드를 이용하여 정렬해서 출력해준다.

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()));
        }

        Collections.sort(numberList);

        for (int currentNumber : numberList) {
            bw.write(currentNumber+"\n");
        }
        bw.flush();
        bw.close();
    }

}

시간복잡도

반복문의 시간복잡도 O(n) 

List.add()의 시간복잡도 O(1)  -> 마지막에 추가하므로 O(1) , 맨앞이나 중간에 삽입했으면 O(n)

 

그러므로 전체 시간복잡도

O(n)

 

다른사람의 풀이

1. 우선순위큐를 이용하여 풀이

우선순위큐를 만들어서 값들을 넣어주면 알아서 정렬이 되므로 따로 정렬메소드를 쓸 필요가 없는 방법이였다.

우선순위큐의 삽입과 삭제는 O(logN)의 시간복잡도를 가진다. 그래서 반복분 시간복잡도 N과 함께

총 시간복잡도 NlogN이 된다.

 

2. 정렬을 직접 구현해서 풀이

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

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

 

 

 

 

 

정리한 개념들

[Java] BufferedReader, BufferedWriter

 

Collections.sort() 와 Arrays.sort() 시간복잡도, 사용법

 

[Java] ArrayList, LinkedList