[JAVA] 백준 2751번 문제, 수 정렬하기 2

<문제 링크>

 

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

---

<풀이>

 

문제에서 중요하게 봐야 할 키워드는 '주어진 입력의 범위는 -1,000,000 ~ 1,000,000인 정수', '수는 중복되지 않는다'입니다.

중복 없이 입력받기 때문에 해당하는 수가 들어왔는지, 아닌지만 판단하면 됩니다.

따라서 크기 200만 인 Boolean 타입의 배열 arr[]를 만들어 값이 들어왔을 경우 True값을 넣어줍니다.

그래서 위의 작업을 첫 번째 for문에서 수행합니다.

두 번째 for문을 설명하기 전에 StringBuilder에 대해서 이야기하겠습니다.

최대 100만 개를 입력받는다면 println()가 100만 번 호출되는 것입니다. 자바에서 println()은 안전 메서드이기 때문에 100만 번이나 호출되는 건 비효율적입니다.

그래서 출력하는 시간을 단축시키기 위해 StringBuilder 객체인 sb를 선언해 출력 값들을 모아 마지막에 한 번에 출력하도록 하면 됩니다.

그래서 두 번째 for문에서 arr[i] 값이 True일 경우에, |1,000,000| 으로 맞추기 위해 (인덱스 - 1,000,000)을 해주어 sb에 추가해줍니다.

 

---

<코드>

arr[]: 들어온 값은 True

N: 테스트 케이스

sb: StringBuilder 객체

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class B2751 {
	public static void main(String[] args) throws IOException {
    
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder(); // 시간 아끼기 위해 한 번에 출력
        
		// 절대값 1,000,000 보다 작거나 같은 수 => -1,000,000 ~ +1,000,000
		boolean[] arr = new boolean[2000001]; // 중복 없으니 bool => 카운팅
        
		int N = Integer.parseInt(br.readLine());
        
		for(int i = 0; i < N; i++) { // 입력 받은 수 값 변경
			arr[Integer.parseInt(br.readLine()) + 1000000] = true;
		}
 
		for(int i = 0; i < arr.length; i++) {
			if(arr[i]) {
				sb.append((i - 1000000)).append('\n');
			}
		}
		
		System.out.print(sb);
	}
}