자바(백준) 2751 수 정렬하기 2

📌풀이 방법

이 문제는 카운팅 정렬(계수 정렬)을 이용한 문제였다. 처음 접근했을 때, 선택 정렬을 사용하게 되면 O(n^2)로 시간 초과가 나올 것 같아서 카운팅 정렬을 이용하여 문제를 풀었다. 여기서 visit를 boolean으로 한 이유는 문제에서 중복된 숫자가 없다고 했기 때문에 경우의 수는 숫자가 있다, 없다뿐이다. 그래서 count를 세지 않고 true false로만 구별하여 문제를 풀었다. 

 

📌필요한 개념

카운팅 정렬

 

📌코드

package Sort;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ2751 {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
 
        int test = Integer.parseInt(st.nextToken());
 
        boolean visit[] = new boolean[2000001];
 
        for(int i = 0; i < test; i++){
            st = new StringTokenizer(br.readLine());
            int index = Integer.parseInt(st.nextToken());
            visit[index + 1000000] = true;
        }
 
        for(int i = 0; i < visit.length; i++){
            if(visit[i]) sb.append(i - 1000000 + "\n");
        }
 
        System.out.println(sb);
    }
}