본문 바로가기
코딩테스트/programming_JAVA

[Java] baekjoon_10989 : 수 정렬하기 3

by prometedor 2024. 1. 19.

정렬

수 정렬하기 3 : Bronze1

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

 

10989번: 수 정렬하기 3

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net

 

 

첫 번째 작성한 코드

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {

    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);

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < N; i++) {
      sb.append(num[i]).append("\n");
    }
    bw.write(sb.toString());
    bw.close();
  }
}

 

ㄴ 처음에는 단순하게 Arrays.sort()를 이용했다. 결과는 시간 초과도 발생하지 않았고 정답이 다른 방법을 이용해 시간을 조금이라도 단축해보고 싶었다.

 

두 번째 작성한 코드

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

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

  public static void main(String[] args) throws IOException {

    int[] arr = new int[10001];

    int N = Integer.parseInt(br.readLine());

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

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < arr.length; i++) {
      while (arr[i] > 0) {
        sb.append(i).append('\n');
        arr[i]--;
      }
    }
    bw.write(sb.toString());
    bw.close();
  }
}

 

ㄴ 입력되는 수는 10,000보다 작거나 같은 자연수이므로, 크기가 10001인 배열 arr을 선언하고 모든 원소는 0으로 초기화했다. 이 배열에는 각 숫자의 등장 횟수를 저장하도록 했다.

ㄴ 입력받은 수를 배열의 인덱스로 사용하여 등장 횟수를 증가시키도록 했다.

ㄴ 마지막으로 배열을 처음부터 끝까지 반복하면서, 해당 인덱스의 숫자가 등장한 횟수 만큼 그 숫자를 StringBuilder에 추가했다.

 


 

 

문제점 : 사실 이 문제는 그냥 Arrays.sort()를 이용해서도 해결할 수 있었던 문제였다. 그러나 시간을 조금 더 줄여보는 방법을 기록해두고자 포스팅을 했다.

해결 방법 : 입력받은 수를 배열의 인덱스로 사용하여 등장 횟수를 증가시키도록 했다.

깨달은 바 : 이미 푼 문제를 다른 방법을 시도하여 문제를 풀어보는 것도 의미있는 것 같다!