문제

코드

시도 1 - X

두 숫자가 바뀔 때 a, b를 비교한 후 같다면 1을 출력하는 방식으로 코드를 구현했다.
그런데 시간 초과가 발생했다. 도저히 이유를 모르겠어서 GPT를 이용했다 ...(시도2로)

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

public class _23970 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] a = new int[n];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st1.nextToken());

        int[] b = new int[n];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            b[i] = Integer.parseInt(st2.nextToken());

        if (Arrays.equals(a, b))
            System.out.println(1);
        else
            buble_sort(a, b);
    }

    public static void buble_sort(int[] a, int[] b) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length -1 -i; j++) {
                if (a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    if (Arrays.equals(a, b)) {
                        System.out.println(1);
                        return;
                    }
                }
            }
        }
        System.out.println(0);
    }
}

시도 2 - O

매 swap마다 Arrays.equals()을 호출하는 게 시간 초과의 원인이었다. swap하는 두 수가 같을 때만 Arrays.sort()를 호출하여 시간 복잡도를 줄여 시간 초과 문제를 해결했다.

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

public class _23970 {
    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int[] a = new int[n];
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            a[i] = Integer.parseInt(st1.nextToken());

        int[] b = new int[n];
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++)
            b[i] = Integer.parseInt(st2.nextToken());

        if (Arrays.equals(a, b))
            System.out.println(1);
        else
            buble_sort(a, b);
    }

    public static void buble_sort(int[] a, int[] b) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length -1 -i; j++) {
                if (a[j] > a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                    // 매 swap마다 Arrays.equals() 호출시 시간 초과 발생
                    // 따라서, a[j] == b[j] && a[j+1] == b[j+1]일 때만 Arrays.equals() 호출하도록 바꿔서 해결
                    if (a[j] == b[j] && a[j+1] == b[j+1] && Arrays.equals(a, b)) {
                        System.out.println(1);
                        return;
                    }
                }
            }
        }
        System.out.println(0);
    }
}