코딩테스트 연습 스터디 진행중 입니다. ✍✍✍
Notion : https://www.notion.so/1c911ca6572e4513bd8ed091aa508d67

문제

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

[나의 풀이]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Correct {

    static int bubble_sort(int[] A, int[] B, int n) {

        // A,B 처음부터 같으면 1
        if (Arrays.equals(A, B)) {
            return 1;
        }

        // last, last2 : 정렬이 끝난 인덱스는 for문 돌지 않아도 됌
        int last = n - 1;
        int last2 = 0;
        for (int i = 0; i < n - 1; i++) {
            if (last == 0) {
                break;
            }
            int check = 0;
            for (int j = 0; j < last; j++) {
                if (A[j] > A[j + 1]) {
                    swap(A, j, j + 1);
                    check++;
                    last2 = j;
					
                    // 정렬이 시행될 때마다 모든 원소를 비교할 필요 없이
                    // 바뀐 원소만 체크하여 A ,B 배열 확인
                    if (A[j] == B[j]) {
                        if (Arrays.equals(A, B)) {
                            return 1;
                        }
                    }
                }
            }
            last = last2;
            // 바뀌는 것이 없으면 break;
            if (check == 0) {
                break;
            }

        }

        return 0;
    }

    static void swap(int[] A, int front, int rear) {
        int temp = A[front];
        A[front] = A[rear];
        A[rear] = temp;
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

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

        st = new StringTokenizer(br.readLine());
        int[] A = new int[n];
        for (int i = 0; i < A.length; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        int[] B = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < A.length; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        bw.write(bubble_sort(A, B, n) + "");

        bw.flush();

    }

}

처음으로 백준 골드 문제 풀었습니다!🐸🐸🐸

오늘 교재로 개념 학습한 버블 정렬 알고리즘에 관한 문제를 풀어보았습니다. 버블 정렬은 시간복잡도가 O(n^2)이고 문제 요구사항에 따라 O(n^3)까지 올라갑니다. 이 때문에 여러가지 if문을 통해 시간을 줄이는 것이 중요했습니다.

첫번째로 각 패스를 돌때(n-1,n-2,n-3...) 정렬하는 것이 없으면 그 즉시 버블 정렬이 완료됌을 의미하기 때문에 반환하면 됩니다. 두번째로는 정렬이 끝난 인덱스들을 기억하여 그 다음 패스부터는 생략하는 조건도 설정할 수 있습니다. 마지막으로 문제에서 요구하는 B배열의 정렬 과정 확인하는 과정에서는 정렬한 요소들만 비교하는 방식으로 시간을 크게 줄일 수 있었습니다.🙉🙉🙉

감사합니다😍😍😍