백준 2751번 수 정렬하기2 (JAVA)

자동목차

📌문제

 

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​

📌문제

 

🔹풀이 1

 

 

풀이 방법은 🔎백준 2750번 수 정렬하기 의 풀이 2번과 같다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        
        boolean[] sort = new boolean[2000001];
        for(int i = 0; i< n; i++) {
            int temp = Integer.parseInt(br.readLine());
            if(temp < 0) {
                temp = Math.abs(temp) + 1000000;
                sort[temp] = true;
            }
            else sort[temp] = true;        }

        StringBuilder sb = new StringBuilder();
        for(int i = sort.length-1; i >= 1000001; i--) {
            if(sort[i]) sb.append((-1)*(i-1000000)+"\n");
        }

        for(int i = 0; i <= 1000000; i++) {
            if(sort[i]) sb.append(i+"\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}​

🔹풀이 2 : TreeSet 이용하기

 

 

• 입력에 중복이 없는 수들이 주어지므로, 요소를 자동으로 정렬해주는 TreeSet이용 
• 입력받은 숫자를 TreeSet을 통해 자동 정렬해주고, Iterator를 이용해 출력형식을 맞춰준다음 StringBuilder로 한번에 출력

import java.io.IOException;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{
        int n = readInt();
        //입력에 중복이 없는 수들이 주어지므로, 요소를 자동으로 정렬해주는 TreeSet이용
        Set<Integer> sortTarget = new TreeSet<>();
        for(int i = 0; i < n; i++) {
            sortTarget.add(readInt()); //입력받은 수를 TreeSet에 저장
        }
        StringBuilder sb = new StringBuilder(); //한번에 출력하기 위해 StringBuilder 이용

        //요소를 하나씩 꺼내어 가공하기 위해 Iterator 사용(TreeSet은 리스트 형태로 출력되지만, 문제의 출력 형식은 한줄에 숫자 하나씩이기 떄문에)
        Iterator<Integer> iterator = sortTarget.iterator();

        for(int i = 0; i < n; i++) {
        sb.append(iterator.next() + "\n"); //요소 + 줄 개행을 StringBuilder에 넣음
        }
        System.out.println(sb); //답 출력
    }

    //숫자 하나씩 입력받기
    private static int readInt() throws IOException {
        int out = 0;
        boolean isNegative = false;

        while(true) {
            int n = System.in.read();
            if(n <= 32) return isNegative ? (-1)*out : out;
            else if(n == '-') isNegative = true;
            else out = (out<<3) + (out<<1) + (n-'0');
        }
    }

}

 

 

📌코멘트

 

• 이번 문제는 2초의 시간 안에 최대 1,000,000개의 데이터를 정렬해야 하므로, 효율적으로 코드를 짜지 않으면 시간 초과가 뜰 수 있다. 특히 입/출력에서 많은 시간을 잡아먹으므로 효율적인 입/출력 알고리즘을 짜서 이용하는 것이  포인트이다. 
• 컬렉션은 기본적으로 많은 시간과 용량을 잡아먹으므로 컬렉션을 이용하여 풀 경우 시간 초과가 될 가능성이 높으니 입/출력 성능 개선을 신경써서 해주는 것이 좋다. 

 

 

 

 

 

 

 

끝까지 읽어주셔서 감사합니다 :)

Have a good day🐱

 

 

 

📢 Notice

1. 개발자 준비생이 공부한 내용을 정리한 글입니다. 내용에 오류가 있을 수 있습니다.

2. 위와 같은 이유로 내용에 대한 지적과 조언은 감사하게 받습니다.

3. 이 글의 내용은 계속 공부함으로써 언제든지 추가/수정 될 수 있습니다.