21.08.19 기록

백준 알고리즘 2750 풀이

🎆나의 풀이(메모리 14.8MB, 시간 168ms로 통과)

-정렬할 요소가 없을 때까지(cnt == 0) 정렬을 수행하는 로직이다.

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

  public class B2750 {
      public static void main(String[] args) throws IOException {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          int N = Integer.parseInt(br.readLine());

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

          while(true) {
              int temp = 0;
              int cnt = 0;

              for(int i = 0; i < (N-1); i++) {
                  if(numbers[i] > numbers[i+1]) {
                      temp = numbers[i];
                      numbers[i] = numbers[i+1];
                      numbers[i+1] = temp;
                      cnt++;
                  }
              }
              if(cnt == 0) { break; }
          }

          StringBuilder sb = new StringBuilder();
          for(int i = 0; i < N; i++) {
              sb.append(numbers[i]).append("\n");
          }
          System.out.println(sb);
      }
  }

🎆해설(메모리 14.3MB, 시간 148ms로 통과)

-해설은 버블 정렬, Arrays.sort(), 카운팅 정렬 총 세 가지 방법을 제시한다.

• 카운팅 정렬
  • 장점: 두 수를 비교하는 과정이 없어 빠른 배치가 가능하다.
  • 단점: 새로운 배열을 선언하여 사용하는데, 이 배열의 크기는 기존 배열의 max값에 따라 결정된다.(최악의 경우 메모리 낭비가 매우 심할 수 있다.)
  • 카운팅 정렬 구현 과정 (손으로 쓰면서 이해하기!)
    (1)배열 A의 각 값(x)을 새 배열 B의 인덱스값으로 사용한다. (x의 값이 중복으로 나올 경우 B[x]의 값을 +1 한다.)
    (2)배열 B의 각 값을 누적합으로 변환시킨다.(기존: B[0]=1, B[1]=4 -> 변환: B[0]=1, B[1]=5)
    (3)결과를 담는 새 배열 C를 사용하여 A[?]==x -> B[x]==y -> C[y-1]==x 과정을 거쳐 정렬을 완료한다.
    

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

public class B2750 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        //-1000 < range < 1000 (절댓값으로 인한 범위)
        final int RANGE = 1000;
        boolean[] arr = new boolean[2 * RANGE + 1];

        //arr[1000] = 0, (입력값+1000) 인덱스만 true
        for(int i = 0; i < N; i++) {
            arr[Integer.parseInt(br.readLine()) + 1000] = true;
        }

        //true인 값만 sb에 담아 출력한다.
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            if(arr[i]) { sb.append(i-RANGE).append("\n"); }
        }
        System.out.println(sb);
    }
}