[Java] baekjoon_2751 : 수 정렬하기 2

정렬

수 정렬하기 2 : Silver5

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

 

 

첫 번째 코드 작성

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int num[] = new int[N];
      
        for (int i = 0; i < N; i++) {
          num[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(num);

        for (int i = 0; i < num.length; i++) {
          bw.write(String.valueOf(num[i]));
          bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

 

ㄴ 이렇게 해도 정답이 맞긴 하지만 정렬을 하는 데 시간이 꽤 걸렸다.

 

ㄴ 브론즈도 아니고 실버5가 이정도인가,,,? 하는 생각이 들어 다시 생각해보게 되었다.

 

 

두 번째 코드 작성

import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception {
		
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		boolean[] num = new boolean[2000001];
		StringBuilder sb = new StringBuilder();
		
		for (int i = 0; i < N; i++) {
			num[Integer.parseInt(br.readLine()) + 1000000] = true;
		}
		
		br.close();
		
		for (int i = 0; i < num.length; i++) {
			if (num[i] == true) sb.append((i - 1000000) + "\n");
		}
		
		bw.write(sb.toString());
		bw.close();
	}
}

 

ㄴ 주어진 수의 범위가 -1,000,000에서 1,000,000까지이므로, 해당 범위를 포함하는 크기 2,000,001의 배열 arr을 생성한다.

ㄴ 각 인덱스는 수를 나타내고, 배열의 값은 해당 수가 등장했는지 여부를 나타낸다.

boolean 배열 num

각 수의 등장 여부를 나타내기 위한 배열이다. num[i]는 i - 1000000 수가 등장했는지 여부를 나타낸다.

ㄴ num 배열의 인덱스 i는 -1,000,000에서 1,000,000 사이의 정수를 나타낸다. 그러나 자바 배열은 0부터 시작하므로 음수를 배열의 인덱스로 사용할 수 없다. 따라서 -1,000,000부터 1,000,000까지의 범위를 0부터 2,000,000까지의 인덱스로 매핑하기 위해 i - 1000000을 사용한다.
예를 들면, num[0]은 -1,000,000이 등장했는지 여부, num[1]은 -999,999이 등장했는지 여부, ..., num[2000000]은 1,000,000이 등장했는지 여부를 나타낸다. 배열 num의 크기가 2,000,001인 이유는 0부터 2,000,000까지의 인덱스를 사용하기 위함이다.

StringBuilder sb

출력 결과를 저장하기 위한 StringBuilder이다. 문자열을 연결할 때 StringBuilder를 사용하면 성능이 향상된다.

 

 

ㄴ 시간이 단축된 것을 확인하였다.

 

---

 

 

문제점 : 문제 정답은 맞았지만 1520ms 로 시간이 꽤 걸렸다. 

해결 방법 : 문제는 맞았으니 맞은 사람의 코드를 참고하여 코드를 작성하여 908ms 로 시간을 단축시켰다.

깨달은 바 : 조건을 생각하여 시간을 단축시키는 것도 생각해보도록 해야겠다.