코딩테스트 챌린지

[코딩테스트 챌린지] 백준 2947 나무조각 (java)

zincah 2024. 9. 14. 18:26
반응형

문제

 

문제 탐색하기

1. 정렬 알고리즘 구현하기

문제를 확인해보면 나무 조각 뒤에 쓰인 1 부터 5까지의 수를 오름차순으로 정렬하는 프로그램을 구현하는 문제입니다.

인접한 2개의 숫자를 비교하여 정렬하는 조건을 통해 Bubble Sort (버블정렬) 알고리즘을 구현하라는 문제인 것으로 보입니다. 

 

버블 정렬이란?

두 개의 인접한 원소를 비교하여 정렬하는 알고리즘 방식 입니다. 

데이터를 비교하면서 정렬하는 과정, 정확하게는 데이터를 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬이라고 부르기도 합니다.

시간 복잡도는 O(n^2)로 효율적인 정렬방식은 아니지만 주어진 원소가 5이므로 이 문제에서는 충분히 사용할 수 있는 정렬 방식이라고 생각합니다.

 

버블정렬의 과정

1. 현재 값과 인접한 바로 다음 값을 비교합니다.

2. 현재 값이 다음 값보다 크다면 데이터를 교환합니다.

3. 다음 값으로 이동해서 같은 과정을 반복합니다.

4. 한 라운드가 종료되면 다시 처음으로 돌아가서 처음 주어진 원소의 수 만큼 반복합니다.

 

코드 설계하기

  1. 나무판 뒷면에 쓰여진 수를 배열에 입력
  2. Bubble Sort 진행
    1. 인접한 원소를 비교 (현재 원소 > 다음 원소)
    2. 현재원소가 다음원소보다 크다면 그 둘의 값을 교환
    3. 값이 변경되었기에 배열을 출력
    4. 다음 원소로 이동하여 같은 과정을 반복 (j --> j+1)
    5. 위의 라운드가 종료되면 다시 첫번재 인덱스로 돌아가서 1 ~ 4 의 과정을 반복

 

정답 코드

1) 기본적인 버블 정렬

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

public class WoodPiece {

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

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        // 1. 나무판 뒷면에 쓰여진 수를 배열에 입력
        int[] arr = new int[5];
        for(int i=0; i<5; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 2. bubble sort 진행
        for(int i=0; i<arr.length; i++){
            for(int j=0; j<arr.length-1; j++){

                // 2-1. 인접한 원소를 비교하여 정렬
                if(arr[j] > arr[j+1]){
                    swap(j, j+1, arr); // 2-2. 주어진 원소의 위치를 변경
                    changeLoc(arr); // 2-3. 변경된 배열을 출력
                }
            }
        }
    }

    // # 배열의 위치를 변경하는 메소드
    private static void swap(int i, int j, int[] arr){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // # 배열의 위치가 변경될 때 배열을 출력해주는 메소드
    private static void changeLoc(int[] arr){
        for(int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

 

2) 버블 정렬에 대해서 공부하면서 버블 정렬은 정렬이 완료 된 후에도 배열의 길이만큼 과정을 반복하기 때문에 불필요하게 원소를 비교하는 과정이 있다는 것을 알게 되었습니다. 이 부분을 개선할 수 있는 방법을 작성한 글을 보게되어 다시 코드를 작성하게 되었습니다.

이렇게 진행하면 최선의 경우에도 O(n^2) 의 시간복잡도를 가지는 버블정렬의 시간복잡도를 O(n)으로 변경할 수 있다고합니다.

package backjun;

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

public class WoodPiece {

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

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());

        // 1. 나무판 뒷면에 쓰여진 수를 배열에 입력
        int[] arr = new int[5];
        for(int i=0; i<5; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 2. 정렬이 된 경우에 불필요한 정렬 과정을 진행하지 않기 위해 정렬 체크 변수 선언
        boolean sortChk;

        // 3. bubble sort 진행
        for(int i=0; i<arr.length; i++){
            sortChk = false;

            for(int j=0; j<arr.length-1; j++){

                // 3-1. 인접한 원소를 비교하여 정렬
                if(arr[j] > arr[j+1]){
                    swap(j, j+1, arr); // 3-2. 주어진 원소의 위치를 변경
                    changeLoc(arr); // 3-3. 변경된 배열을 출력
                    sortChk = true;
                }
            }

            // 변수가 false 이면 한 라운드 내에서 한번도 원소를 교환하지 않았단 뜻으로 종료
            if(!sortChk){
                break;
            }
        }



    }

    // # 배열의 위치를 변경하는 메소드
    private static void swap(int i, int j, int[] arr){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // # 배열의 위치가 변경될 때 배열을 출력해주는 메소드
    private static void changeLoc(int[] arr){
        for(int i : arr){
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
반응형