백준 - 단계별로 풀어보기 - JAVA (10단계 : 정렬 (1) / 7문제) (2022.12.29 목)

1단계 : 2750번 / 수 정렬하기

import java.util.Scanner;

public class Main{

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int least;

        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }
        for (int i=0; i<N-1; i++){
            least = i;
            for (int j=i+1; j<N; j++){
                if (arr[j] < arr[least]) {least = j;}
            }
            arr[least] = SWAP(arr[i], arr[i] = arr[least]);
        }
        for (int i = 0; i<N; i++){
            System.out.println(arr[i]);
        }

    }

    public static int SWAP(int x, int y){
        return x;
    }
}

 

* N개의 원소가 있는 배열에서 N , N-1, N-2 , ... 번 탐색을 통해서 작은 수 순서대로 정렬하는 선택정렬을 사용

* 두 원소간의 자리를 바꾸어주는 SWAP을 이용

---

2단계 : 2587번 / 대표값2

import java.util.Scanner;

public class Main{

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);

        int[] arr = new int[5];
        for(int i=0; i<5; i++){
            arr[i] = sc.nextInt();
        }

        selection_sort(arr, 5); // arr 정렬

        // 평균
        int sum = 0;
        for (int i=0; i<5; i++){
            sum += arr[i];
        }
        int avg = sum / 5;

        // 중앙값
        int mid = arr[2]; // 0, 1, 2, 3, 4
    
        System.out.println(avg);
        System.out.println(mid);
    }

    public static int SWAP(int x, int y){
        return x;
    }

    public static void selection_sort(int array[], int N){
        int least;
        for (int i=0; i<N-1; i++){
            least = i;
            for (int j=i+1; j<N; j++){
                if (array[j] < array[least]) {least = j;}
            }
            array[least] = SWAP(array[i], array[i] = array[least]);
        }
    }
}

---

3단계 : 25305번 / 커트라인

import java.util.Scanner;

public class Main{

    public static void main(String args[]){

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 웅시자 수
        int k = sc.nextInt(); // 수상자 수

        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        selection_sort(arr, N); // arr 정렬

        // 커트라인 : arr[N-k]
        System.out.println(arr[N-k]);
    }

    public static int SWAP(int x, int y){
        return x;
    }

    public static void selection_sort(int array[], int N){
        int least;
        for (int i=0; i<N-1; i++){
            least = i;
            for (int j=i+1; j<N; j++){
                if (array[j] < array[least]) {least = j;}
            }
            array[least] = SWAP(array[i], array[i] = array[least]);
        }
    }
}

---

4단계 : 2751번 / 수 정렬하기 2

[1단계 : 2750번 / 수 정렬하기] 에서 사용한 선택 정렬의 방법으로는 O(N^2)의 시간 복잡도로 인해 시간내 문제를 해결할 수 없다.

위 설명과 같이 내장 함수를 사용하여 해결하였다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

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

        ArrayList<Integer> nums = new ArrayList<Integer>();

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

        Collections.sort(nums);

        for (int i=0; i<N; i++){
            bw.write(nums.get(i)+"\n");
        }

        bw.flush();
    }
}

Collections 라이브러리의 정렬 기능인 sort() 메소드를 사용하여 정렬하였다.

이때, 기존 입출력 방식인 Scanner를 사용한 경우 '시간 초과'가 발생하여, BufferedReader 방식을 사용하여 해결하였다.

BufferedReader + Collections.sort()

---

5단계 : 10989번 / 수 정렬하기 3

카운팅 정렬을 구현하여 해결하였다.

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

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[] arr = new int[N];

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

        arr = CountingSort(arr, N);
        
        for (int i=0; i<N; i++){
            bw.write(arr[i]+"\n");
        }

        bw.flush();
    }

    public static int[] CountingSort(int[] array, int N){

        // 1. 배열에서 가장 큰 값 찾기
        int max=0;
        for(int i=0; i<N; i++){
            if (array[i] > max) {max = array[i];}
        }

        // 2. Count Array 생성 (size = max + 1)
        int[] CountArray = new int[max+1]; // init : 0
        for(int i=0; i<N; i++){
            CountArray[array[i]]++;
        }

        // 3. 누적 Count Array 생성
        for(int i=1; i<max+1; i++){
            CountArray[i] += CountArray[i-1];
        }

        // 4. 누적 Count Array 모든 원소 -1
        for(int i=0; i<max+1; i++){
            CountArray[i]--;
        }

        // 5. 정렬
        int[] sortedArray = new int[N];
        for(int i=N-1; i>-1; i--){
            sortedArray[ CountArray[array[i]] ] = array[i];
            CountArray[array[i]]--;
        }

        return sortedArray;
    }
}

---

6단계 : 2108번 / 통계학

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

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

        int[] arr = new int[N];

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

        double sum = 0;
        // 1. 산술평균
        for(int i=0; i<N; i++){
            sum += arr[i];
        }
        double avg;
        avg = sum/N;
        bw.write(Math.round(avg)+"\n"); // 소수점 일의자리에서 반올림

        // 2. 중앙값
        Arrays.sort(arr); // 정렬
        bw.write(arr[N/2]+"\n");
        
        // 3. 최빈값
        int max=-4001; int min=4001;
        for(int i=0; i<N; i++){
            if (arr[i] > max) {max = arr[i];}
            if (arr[i] < min) {min = arr[i];}
        }


        int[] CountArray = new int[8001]; // init : 0
        for(int i=0; i<N; i++){
            CountArray[arr[i] + 4000]++; // ex) -2001은 1999에 저장
        }

        int a = 0; int index = 0;
        for(int i=0; i<N; i++){
            if (CountArray[arr[i] + 4000]>a){
                a = CountArray[arr[i] + 4000]; index = arr[i];
            }
        }

        int count = 0; // 최빈값의 개수
        for(int i=0; i<8001; i++){
            if (CountArray[i] == a){
                count++;
            }
            if (count == 2){index = i-4000; break;}
        }

        bw.write(index+"\n");

        // 4. 범위
        bw.write(max-min+"\n");

        bw.flush();
    }
}

---

7단계 : 1427번 / 소트인사이드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;

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());
        ArrayList<Integer> arr = new ArrayList<Integer>();

        // 자리수 구하기
        int count = 1;
        int count_N = N;
        while(count_N / 10 != 0){
            count_N = count_N/10;
            count++;
        }

        for(int i=0; i<count; i++){
            arr.add(N%10); N=N/10;  
        }
        Collections.sort(arr, Collections.reverseOrder()); // 내림차순

        for(int i=0; i<count; i++){
            bw.write(arr.get(i)+"");
        }
        bw.write("\n");

        bw.flush();
    }
}

---