[Java][백준-2751] 수 정렬하기 2

문제

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

 

요구사항 확인

-숫자는 최대 1백만개 주어지며, 중복되지 않는다.

-숫자는 정수, 즉 양수, 음수, 0이 주어진다.

-개수가 많기 때문에 빠른 알고리즘이 요구된다.

 

코드 설계

int idx = 1000000;
boolean[] booleanA = new boolean[idx];
boolean[] booleanB = new boolean[idx];

양수와 음수 등장여부를 받을 수 있는 boolean 배열을 초기화한다. 속도를 위해 boolean 형태를 선택했다.

 

 

 

boolean zero = false;	//숫자 0 등장여부
int count = Integer.parseInt(bufferedReader.readLine());
int i = 0;

while (i < count) {
	int input = Integer.parseInt(bufferedReader.readLine());

	if (!zero && input == 0) {	//조건문
		zero = true;
		i++;
		continue;
	}
	getNumber(booleanA, booleanB, input);
	i++;
}

count 개수만큼 반복문을 돈다. 조건문을 거치면서 0 이 나왔는지 확인한다. getNumber() 메서드를 호출해 입력받은 숫자를 넘겨준다.

 

 

 

private void getNumber(boolean[] booleanA, boolean[] booleanB, int input) {
	if (input < 0) {
		booleanA[Math.abs(input) - 1] = true;
	} else {
		booleanB[input - 1] = true;
	}
}

음수, 양수에 따라 각 인덱스에 해당하는 값을 true로 바꿔준다. Math.abs() 는 절대값을 반환해준다.

 

 

 

private void printNumber(boolean[] booleanA, boolean[] booleanB, boolean zero) {
	StringBuilder sb = new StringBuilder();
	String newLine = "\n";
	int count;
	int i;

	count = booleanA.length;
	i = 0;

	while (i < count) {
		i++;
		int idx = count - i;
		if (booleanA[idx]) {
			sb
			.append("-")	//음수이므로 앞에 '-'를 붙여준다
			.append(idx + 1)
			.append(newLine)
			;
		}
	}

	if (zero) {	//0이 등장했다면
		sb.append(0).append(newLine);
	}

	count = booleanB.length;
	i = 0;

	while (i < count) {
		if (booleanB[i]) {
			sb.append(i + 1).append(newLine);
		}
		i++;
	}

	bufferedWriter.write(sb.toString());
}

두 boolean 배열문을 돌면서 true에 해당하는 인덱스를 출력한다.

 

전체 코드

import java.io.*;

public class Main {
    private Reader reader;
    private Writer writer;
    private BufferedReader bufferedReader;
    private BufferedWriter bufferedWriter;

    public static void main(String[] args) {
        new Main().execute();
    }

    private void execute() {
        try{
            resourceOpen();
            int idx = 1000000;
            boolean[] booleanA = new boolean[idx];
            boolean[] booleanB = new boolean[idx];
            int count = Integer.parseInt(bufferedReader.readLine());
            boolean zero = false;
            int i = 0;

            while (i < count) {
                int input = Integer.parseInt(bufferedReader.readLine());

                if (!zero && input == 0) {
                    zero = true;
                    i++;
                    continue;
                }
                getNumber(booleanA, booleanB, input);
                i++;
            }

            printNumber(booleanA, booleanB, zero);
            bufferedWriter.flush();
        } catch (IOException ignored){
        } finally {
            try {
                resourceClose();
            } catch (IOException io){
                io.printStackTrace();
            }
        }
    }

    private void getNumber(boolean[] booleanA, boolean[] booleanB, int input) {
        if (input < 0) {
            booleanA[Math.abs(input) - 1] = true;
        } else {
            booleanB[input - 1] = true;
        }
    }

    private void printNumber(boolean[] booleanA, boolean[] booleanB, boolean zero) throws IOException {
        StringBuilder sb = new StringBuilder();
        String newLine = "\n";
        int count;
        int i;

        count = booleanA.length;
        i = 0;

        while (i < count) {
            i++;
            int idx = count - i;
            if (booleanA[idx]) {
                sb
                .append("-")
                .append(idx + 1)
                .append(newLine)
                ;
            }
        }

        if (zero) {
            sb.append(0).append(newLine);
        }

        count = booleanB.length;
        i = 0;

        while (i < count) {
            if (booleanB[i]) {
                sb.append(i + 1).append(newLine);
            }
            i++;
        }

        bufferedWriter.write(sb.toString());
    }
    private void resourceOpen(){
        reader = new InputStreamReader(System.in);
        writer = new OutputStreamWriter(System.out);
        bufferedReader = new BufferedReader(reader);
        bufferedWriter = new BufferedWriter(writer);
    }

    private void resourceClose() throws IOException {
        if (reader != null) {
            reader.close();
        }
        if (writer != null) {
            writer.close();
        }
        if (bufferedReader != null) {
            bufferedReader.close();
        }
        if (bufferedWriter != null) {
            bufferedWriter.close();
        }
    }
}