[백준/JAVA] 2751번: 수 정렬하기 2

🔺 문제

2751번: 수 정렬하기 2

 

🔺 코드

- 풀이1) Collections.sort() 사용

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder  sb = new StringBuilder();
        
        int n = Integer.parseInt(br.readLine());
 
        List<Integer> list = new ArrayList<>();
        for(int i=0 ; i<n ; i++) {
            list.add(Integer.parseInt(br.readLine()));
        }
        Collections.sort(list);
        
        for(int i : list) {
            sb.append(i).append('\n');
        }
        System.out.println(sb);
    }
}

배열 만들고 Arrays.sort() 쓰면 시간초과 에러가 난다...

그래서 리스트 만들고 Collections.sort() 써줘야 한다.

출처 : https://www.acmicpc.net/board/view/31887

 

아 그리고 출력할 때 for문으로 바로 돌리면 시간 초과 에러가 뜨더라... 

StringBuilder 이용해서 출력해줘야 속도가 빠르고 부하가 적기 때문이라고 함...

 

 

- 풀이2) 카운팅 정렬

수의 범위가 -1000000 ~ 1000000이며,

기준점 0을 1000000번째 인덱스로 생각하는 거라고 한다... (카운팅 정렬)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        boolean[] arr = new boolean[2000001];    
        
        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);
    }
}

이 해결법 참고한 사이트는 아래에..

 

 

- 풀이3) 병합 정렬 사용(시간 복잡도 : Onlogn)

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] A, tmp;
    
    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());
        A = new int[N + 1];    // 숫자 배열
        tmp = new int[N + 1];  // 정렬 시 사용할 임시 배열
        
        for(int i = 1 ; i <= N ; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        
        merge_sort(1, N);
        
        for(int i = 1;  i <= N ; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        br.close();
    }
    
    public static void merge_sort(int s, int e) {
        /** 1. 분할 **/
        if(e - s < 1)   return;
        int m = s + (e - s) / 2;
        
        // 📍 재귀 함수 형태로 구현 📍
        merge_sort(s, m);
        merge_sort(m + 1, e);
        
        // tmp 배열 저장하기
        for(int i = s ; i <= e ; i++) {
            tmp[i] = A[i];
        }
        
        /** 2. 정복 **/
        int l = s;
        int r = m + 1;
        int idx = s;
        
        while(l <= m && r <= e) {
            if(tmp[l] < tmp[r]) {
                A[idx] = tmp[l];
                idx++;
                l++;
            }
            else {
                A[idx] = tmp[r];
                idx++;
                r++;
            }
        }
        
        // 🔔 한쪽 그룹이 모두 선택한 후 남은 값 정리하기 
        while(l <= m) {
            A[idx] = tmp[l];
            idx++;
            l++;
        }   
        while(r <= e) {
            A[idx] = tmp[r];
            idx++;
            r++;
        }
    }
}

---

(+ 6/12 2회독)

import java.util.*;
import java.io.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int N = Integer.parseInt(br.readLine());
        long[] A = new long[N];
        
        
        for(int i = 0 ; i < N ; i++) {
            A[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(A);
        
        for(long l : A) {
            sb.append(l).append("\n");
        }
 
        System.out.println(sb);
    }
}

아마도.. 카운팅 정렬 써야했던 거겠지...

 

 

---

(참고)

- 풀이

[백준] 2751번 : 수 정렬하기 2 - JAVA [자바]

[백준] 2751번. 수 정렬하기 2 (Java)

 

✔ 카운팅 정렬

자바 [JAVA] - 카운팅 정렬 (Counting Sort / 계수 정렬)

알고리즘 - Counting Sort (카운팅 정렬 / 계수 정렬) 알고리즘