[소프티어] 통근버스 출발 순서 검증하기 in Java

📜 문제

문제 링크

❌ 나의 풀이 (오답)

1. 가능한 (i, j, k)의 모든 순서쌍을 조합을 사용해서 구한다.
2. 1에서 구한 순서쌍으로 ai < aj, ai > ak인 경우 순서대로 출발할 수 없으므로, answer를 1 증가시킨다.

이 문제에서 입력값 범위가 3 이상 5000 이하인데,
ijk 순서쌍을 조합으로 구하게 되면 O(N^3)의 시간복잡도가 되기 때문에 시간초과가 난다.
(O(N^3)을 제출할 생각을 한 나도 참..하핫😅)

⌨️ 오답 코드

import java.util.*;
import java.io.*;


public class ValidateBusOrder
{
    private static Long answer = 0L;
    private static int n;
    private static ArrayList<int[]> combinations = new ArrayList<>();
    private static ArrayList<Integer> tmpCombinations = new ArrayList<>();
    private static int[] busNumbers;
    private static boolean[] visited;

    public static void main(String args[]) throws IOException
    {
        init();
        combination(0);

        for (int i = 0; i < combinations.size(); i++) {
            if (!isValidSequence(i)) {
                answer++;
            }
        }

        System.out.print(answer);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        busNumbers = new int[n + 1];
        visited = new boolean[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int busNumber = Integer.parseInt(st.nextToken());
            busNumbers[i] = busNumber;
        }
    }

    private static void combination(int start) {
        if (tmpCombinations.size() == 3) {
            combinations.add(new int[]{tmpCombinations.get(0), tmpCombinations.get(1), tmpCombinations.get(2)});
            return;
        }

        for (int i = start + 1; i <= n; i++) {
            tmpCombinations.add(i);
            combination(i);
            tmpCombinations.remove(tmpCombinations.size() - 1);
        }
    }

    private static boolean isValidSequence(int index) {
        int[] ijk = combinations.get(index);
        int i = ijk[0]; int j = ijk[1]; int k = ijk[2];

        if (busNumbers[i] < busNumbers[j] && busNumbers[i] > busNumbers[k]) {
            return false;
        } else {
            return true;
        }
    }
}

⭕️ 정답 풀이

문제 유형은 구간합 문제이다.
1. 구간합에 사용할 이차원 배열 arr[x][j]를 "버스 번호가 담긴 리스트에서 j번째 이후에 있는 것들 중에 x보다 번호가 작은 것들의 수"를 의미하도록 정의한다.

• 이렇게 세운 이유는, 버스 번호가 담긴 리스트를 끝에서부터 순회하면, arr[x][j - 1]은 arr[x][j]가 x보다 큰지 작은지 여부에 따라 O(1)만에 구해지므로 시간적으로 효율적이기 때문이다.
• x의 범위는 1 이상 n 이하이고, j의 범위는 1 이상 n - 1 이하이기 때문에 arr배열을 O(n^2)만에 채울 수 있다.

2/. ai < aj일 때 ak < ai인 경우를 찾아낸다.

• i < j인 i, j를 설정하고, arr[x][j]에서 x의 자리에 "i번째의 버스 번호"의 의미를 대입한다.
  그러면 arr[x][j]는 자연스럽게 i < j < k를 만족하는 k 중에서 ak < ai인 경우의 수를 의미하게 된다.

⌨️ 정답 코드

import java.util.*;
import java.io.*;

public class ValidateBusOrder
{
    private static Long answer = 0L;
    private static int n;
    private static int[] busNumbers;
    private static int[][] arr; // arr[x][j] : busNumbers의 j번째보다 이후에 있는 것들 중에 x보다 작은 것들의 수

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

        for (int x = 1; x <= n; x++) {
            for (int j = n - 1; 0 < j; j--) {
                if (busNumbers[j + 1] < x) {
                    arr[x][j] = arr[x][j + 1] + 1;
                } else {
                    arr[x][j] = arr[x][j + 1];
                }
            }
        }

        for (int i = 1; i <= n - 2; i++) {
            for (int j = i + 1; j <= n - 1; j++) {
                // ai < aj일 때 ak < ai인 경우의 수를 answer에 더함
                // busNumbers에서 j번째보다 이후에 있는 버스 번호 중 busNumbers[i]보다 작은 것들의 개수를 answer에 더함
                if (busNumbers[i] < busNumbers[j]) {
                    answer += arr[busNumbers[i]][j];
                }
            }
        }

        System.out.print(answer);
    }

    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n + 1][n + 1];
        busNumbers = new int[n + 1];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            int busNumber = Integer.parseInt(st.nextToken());
            busNumbers[i] = busNumber;
        }
    }
}

😄 느낀 점

문제 유형이 구간합이라고 하지만, 동적 계획법에서 점화식을 세우는 것만큼 배열 arr를 설정하는 것이 까다로웠다.
만약 이게 코딩테스트 문제로 나왔다면 저 풀이방법을 생각해내지 못했을 것 같다🥲
코딩테스트에서 만나지 않고 연습문제로 만나게 되어서 참 다행이다.