[JAVA] 백준 2947_나무 조각

 

[문제링크]

https://www.acmicpc.net/problem/2947

 

 

 

📌 문제 탐색하기

무작위로 입력된 1부터 5까지의 숫자조각을 1 2 3 4 5 순서로 정렬하는 문제이다. 

배열의 인접한 두 숫자를 비교하여 큰 숫자를 뒤로 가도록 순서를 변경하는 버블 정렬을 활용하는 문제이다.

두개의 숫자의 위치가 변경될 때마다 숫자 배열을 출력해야한다.

 

📌 가능한 시간복잡도

버블 정렬의 시간복잡도는 크게 2가지로 나뉜다.

 

1. 평균적 & 복잡한 시간복잡도

    : N개의 숫자를 입력받아 배열의 길이가 n인 경우 각각의 요소를 최대 (n-1)번 비교해야하기 때문에 시간 복잡도 O(N^2)       을 갖는다.

2. 간단하고 짧은 시간복잡도

    : 이미 정렬이 완료된 상태의 배열으로 입력된 경우 한번의 반복으로 정렬이 완료되기 때문에 비교적 간단한 시간

      복잡도 O(N) 을 갖는다. 

 

따라서, 가능한 시간복잡도는 O(N^2) 입니다.

해당 문제에서 주어진 최대 크기가 5이기 대문에 문제가 되지 않을것으로 보인다.

 

📌 코드 설계하기

1. 1 2 3 4 5 의 정렬된 순서가 될 때까지 반복해야하기 때문에 while 반복문을 활용하고 sorted로 배열의 정렬 상태를 확인하고 정렬된 상태이면 break; 로 반복문 종료하면 된다. 

2. 두개의 숫자를 비교해서 큰 숫자를 뒤로 가도록 순서를 변경해야하므로 wood[i] > wood[i+1] 으로 두개의 숫자를 비교해서 순서를 바꾸고 출력하기

3. 숫자 자리 바뀔때마다 배열 출력해야함!!! => for문 사용해서 출력

 

📌 정답 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

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

        while (true) {
            boolean sorted = true; 
            for (int i = 0; i < 4; i++) { 
                if (wood[i] > wood[i + 1]) {
                    int temp = wood[i];
                    wood[i] = wood[i + 1];
                    wood[i + 1] = temp;
                    
                    for (int j = 0; j < 5; j++) {
                        System.out.print(wood[j] + " ");
                    }
                    System.out.println();
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }
}