백준 2751번 자바 문제 답/해설(수 정렬하기 2 문제)

[1] 백준 카테고리
단계별로 풀어보기
정렬

2단계 수 정렬하기 2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

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

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

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

3. 예제 입력 1
5

5

4

3

2

1

4. 예제 출력 1
1
2
3
4
5

[3] 정답
1. 정답 해설 미포함

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        int N = Integer.parseInt(br.readLine());
        ArrayList<Integer> arr = new ArrayList<>();
 
        for (int i = 0; i < N; i++) {
            arr.add(Integer.parseInt(br.readLine()));
        }
        
        Collections.sort(arr);
 
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(arr.get(i) + "\n");
        }
 
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

 

2.정답 해설 포함

import java.io.BufferedReader;
/* BufferedReader 사용을 위해서 java.io.BufferedReader 클래스를 import 한다.
Enter를 경계로 인식하고 받은 데이터는 String으로 고정된다.*/
import java.io.BufferedWriter;
/* BufferedWriter 사용을 위해서 java.io.BufferedWriter 클래스를 import 한다.
System.out.print와 같은 역활을 하지만 버퍼를 이용하기 때문에 성능면에서 우위에 있다. 
사용하는 메소드는 Write(), flush(), close()가 있다.*/
import java.io.InputStreamReader;
/* InputStreamReader 사용을 위해서 java.io.InputStreamReader 클래스를 import 한다.
byte 단위 데이터를 문자 단위 데이터로 처리할 수 있도록 변환해주기 위해서
InputStreamReader를 사용한다. */
import java.io.OutputStreamWriter;
/* OutputStreamWriter 사용을 위해서 java.io.OutputStreamWriter 클래스를 import 한다.
문자 단위 입출력을 할 수 있게된다. 문자열을 처리 할 수 있다.*/
import java.util.ArrayList;
// ArrayList 사용을 위해서 java.util.ArrayList 클래스를 import 한다.
import java.util.Collections;
// sort 메소드 사용을 위해서 java.util.Collections 클래스를 import 한다.
 
public class Main {
// 접근제어자 public으로 Main 클래스를 선언한다.
	public static void main(String[] args) throws Exception {
	/* 접근제어자 public으로 메모리에 상주하게 리턴값이 없이 main 함수를 선언한다.
	예외처리로 IOException를 포함한다.*/	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader 객체 br를 선언한다
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		// BufferedWriter 객체 bw를 선언한다

		int N = Integer.parseInt(br.readLine());
		// 변수 n에 값을 공백 단위로 구분해서 입력받는다.
		ArrayList<Integer> arr = new ArrayList<>();
		// ArrayList arr를 선언한다 타입은 Integer 이다.

		for (int i = 0; i < N; i++) {
		// for문을 선언한다 i가 0~<N까지 괄호안의 코드가 반복된다.
			arr.add(Integer.parseInt(br.readLine()));
			/* add 메소드를 사용해서 개행으로 배열 arr[N]에 값을 입력한다.
			리스트에 마지막에 데이터가 추가되게 된다.*/
        }

		Collections.sort(arr);
		// Collections 클래스의 메소드 sort를 사용한다. 배열 arr를 오름차순 정렬한다.

		StringBuilder sb = new StringBuilder();
		/* StringBuilder 객체 sb를 선언한다. 문자열을 더할때 기존에 데이터에
		더하게 된다. */
		
		for (int i = 0; i < N; i++) {
		// for문을 선언한다 i가 0~<N까지 반복한다.
			sb.append(arr.get(i) + "\n");
			// 객체 sb의 메서드 append를 호출한다. 배열 arr[i]가 계속해서 추가되게 된다.
        }
 
		bw.write(sb.toString());
		// 객체 sb의 값을 String 객체를 생성한 후 write 메소드를 사용해서 출력한다.
		bw.flush();
		// 메소드 flush()를 사용한다. 버퍼에 저장되어 있는 내용을 클라이언트에 전송하고 버퍼를 비운다.
		bw.close();
		// 객체 bw를 사용을 종료한다.
		br.close();
		// 객체 br 사용을 종료한다.
    }
}

  2750번과 같은 정렬문제이지만 N의 범위가 천배로 늘어났기 때문에 같은 알고리즘으로 풀면 시간 초과가 나게된다. 필자의 경우 2750번을 퀵 정렬중 하나인 버블 정렬로 풀었는데, 퀵 정렬은 최대 걸리는 시간이 O(N^2)이므로 퀵 정렬로 풀면 시간 초과가 나게 된다.  Array.sort의 경우에도 최대로 걸리는 시간이 O(N^2)가 걸리게 된다.

  즉, 시간초과가 안나게 하기 위해서는 시간 복잡도가 적은 알고리즘을 사용해야 하는 것이다. 필자의 경우 Timsort인 Collections.sort()를 사용하였다. Timsort의 경우 합병정렬과 삽입정렬를 섞은 알고리즘을 사용한다. Timsort는 시간 복잡도가 O(n) ~ O(nlogn)이므로 이 문제같이 시간이 촉박한 경우에 사용하면 된다.

 

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

 Collections.sort()는 일반적인 배열로 사용할 수 없고 리스트를 사용해야 한다. 그래서 ArrayList를 사용하였다. 

 

		Collections.sort(arr);

Collection 클래스의 sort 메소드를 사용해서 ArrayList arr를 오름차순 정렬하였다.

 

[4] 결과