[Baekjoon 11931] 수 정렬하기 4 - JAVA

[Silver V] 수 정렬하기 4 - 11931

문제 링크

성능 요약

메모리: 102532 KB, 시간: 844 ms

분류

정렬

문제 설명

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

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 내림차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

문제 풀이

해당 문제는 sort와 우선순위 큐를 사용하면 Scanner와 print를 사용하면 시간초과가 발생한다.

그래서 정렬과 우선순위 큐를 사용해서 시간초과가 발생했다면 BufferedReader와 BufferedWritter로 입, 출력을 받으면 해결된다.

또한 정렬과 우선순위 큐를 사용하지 않고 문제를 풀수도있다.

이 경우에는 StringBuilder를 사용해서 출력했다.

사실 시간초과만 해결하면 그리 어려운 문제는 아니다....

우선순위 큐를 사용해서 풀기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.PriorityQueue;

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

    // 수의 개수 N을 입력
    int N = Integer.parseInt(br.readLine());

    // 우선순위 큐(Priority Queue)를 생성
    PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Integer.compare(b, a));

    // N개의 수를 입력받아 우선순위 큐에 추가
    for (int i = 0; i < N; i++) {
      int num = Integer.parseInt(br.readLine());
      pq.offer(num);
    }

    // 우선순위 큐에서 수를 꺼내면서 출력
    while (!pq.isEmpty()) {
      int num = pq.poll();
      bw.write(Integer.toString(num));
      bw.newLine();
    }

    bw.flush();
    bw.close();
    br.close();
  }
}

정렬을 사용해서 풀기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
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));

    // 수의 개수 N을 입력
    int N = Integer.parseInt(br.readLine());

    // 수를 저장할 배열을 생성
    int[] arr = new int[N];

    // N개의 수를 입력받아 배열에 저장
    for (int i = 0; i < N; i++) {
      arr[i] = Integer.parseInt(br.readLine());
    }

    // 배열을 내림차순으로 정렬
    Arrays.sort(arr);

    // 정렬된 배열을 역순으로 출력
    for (int i = N - 1; i >= 0; i--) {
      bw.write(Integer.toString(arr[i]));
      bw.newLine();
    }

    bw.flush();
    bw.close();
    br.close();
  }
}

정렬과 큐를 사용하지 않고 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

    int arr[] = new int[2000001];

    int N = Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
      int M = Integer.parseInt(br.readLine());

      arr[M + 1000000]++;
    }
    for (int i = 2000000; i >= 0; i--) {
      for (int j = 0; j < arr[i]; j++) {
        sb.append((i - 1000000)).append("\n");
      }
    }
    System.out.print(sb);
  }
}

코드 풀이

배열의 값을 빈도수에 따라 내림차순으로 출력하는 방식으로 동작하도록 했다.

    int arr[] = new int[2000001];

    int N = Integer.parseInt(br.readLine());
    for (int i = 0; i < N; i++) {
      int M = Integer.parseInt(br.readLine());

      arr[M + 1000000]++;
    }

• 수의 개수를 세기 위해 크기가 2000001인 배열을 선언한다.
• 입력 받을 변수 N을 선언한다.
• N번만큼 돌아가면서 M에 값을 입력한다.
• arr 배열의 인덱스를 M + 1000000로 지정하고 값을 증가시킨다.

    for (int i = 2000000; i >= 0; i--) {
      for (int j = 0; j < arr[i]; j++) {
        sb.append((i - 1000000)).append("\n");
      }
    }

• sb에 (i - 1000000) 값을 추가하고 개행 문자를 추가한다.