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

https://softeer.ai/practice/6257

 

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

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

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

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

---

1.  아이디어

 

(a, b, c)가 스택 정렬이 불가능한 경우는 a, b, c에서 나올 수 있는 6가지 경우의 수 중 a < b 이면서 a > c 인 경우 하나 뿐이다. N이 최대 5000까지여서 3중 for문을 활용한 간단한 구현은 시간 초과가 발생하는데 이를 해결하기 위해 다이나믹 프로그래밍을 활용해 O(N^2)으로 구현했다.

---

2. 문제풀이

 

스택 정렬이 불가능한 조합을 찾기 위해 dp 테이블을 활용했다. dp 테이블에는 주어진 수 i, j에 대해 i보다 큰 j를 발견했을 때 j 이후로 등장하는 i보다 작은 수의 개수를 저장했다. 이를 위해 열 인덱스를 역순으로 순회하며 바로 이전 값을 채워준 후 i > j면 +1을 해주도록 했다.

이후 다시 2중 for문을 순회하며 i보다 큰 j를 발견했을 때 dp 테이블에서 바로 j 이후로 등장할 i보다 작은 수의 개수를 찾도록 구현했다. 이때 순서쌍의 수가 int형의 범위를 넘어갈 수 있음에 주의해야 한다.

---

3. 코드

 

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

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

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

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

        int[][] dp = new int[N][N + 1];
        for (int i = 0; i < N - 1; i++) {
            for (int j = N - 1; j > i; j--) {
                dp[i][j] = dp[i][j + 1];
                if (arr[i] > arr[j]) dp[i][j]++;
            }
        }

        // int형 오버플로우 발생 주의
        long cnt = 0;
        for (int i = 0; i < N - 1; i++) {
            for (int j = i + 1; j < N; j++) {
                if (arr[i] < arr[j]) cnt += dp[i][j + 1];
            }
        }

        System.out.println(cnt);
    }
}

---

4. 후기