[BOJ] 백준 2751 - 수 정렬하기 2 (자바)

음수가 있는지 모르고 엄청 헤맨 문제;;

첫째 줄에 수의 개수 N(1<=N<=1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 라는 문구를 제대로 이해하지 못했다.

즉, 음수도 가능하다는 얘기

그렇다면 음수와 양수를 어떻게 나눌 것인가에 대한 문제가 생긴다. 

배열 위치는 항상 양수만 가능하기 때문에 (arr[-900]같은 음수들은 존재 불가)

나는 0~1000000까지는 음수를 저장하는 변수로 1000001~2000000 은 양수를 저장하는 변수로 만들었다.

처음에 1000000을 더해주고 결과를 낼때는 1000000을 빼주면 된다.

예를들어) -1000000은 Arr[0]에 저장되고, 나올때 -1000000의 값을 빼기때문에 결과는 큰 상관이 없다.

그리고 Count Sorting을 이용하여 문제를 풀었다.

import java.io.FileInputStream;
import java.util.Scanner;
 
public class Main {
    public static void main(String args[]) throws Exception {
        // Scanner sc = new Scanner(System.in);
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
 
        Integer a=  null;
        int N = sc.nextInt();
        int size = 2000000;
        int[] arr = new int[size + 5];
        for (int i = 1; i <= N; i++) {
            //Count Sorting... 해당 값의 위치를 1로 바꿔준다.
            //음수가 있기 때문에 1000000을 더해준다.
            arr[sc.nextInt() + 1000000] = 1;
        }
        for (int i = 0; i <= size; i++) {
            //모두 출력했는데 계속해서 반복문을 돌 수 있으니깐 N==0일때 종료되게 해준다.
            if(N==0) break;
            //Count Sorting이기 때문에 배열이 0이면 넘어간다. 
            if (arr[i] != 0) {
                System.out.println(i-1000000);
                N--;
            }
        }
    }
}