Table of contents

백준 가장 긴 바이토닉 부분 수열

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

증가 부분 수열과, 감소 부분 수열을 응용한 dp 문제인 것 같다.

가장 긴 증가 부분 수열

자신보다 작은 숫자들의 부분수열에서 길이가 가장 큰 경우를 구해야 한다. 자신보다 작은 숫자들의 부분수열에서 길이가 같은 경우는 하나만 선택해도 상관없다.

maxLengthOfSmallerNumbers(i) = dp[i] = maxLengthOfSmallerNumbers(i) + 1

i 0 1 2 3 4 5 6
numbers 0 10 20 10 30 20 50
dp 0 1 2 1 3 2 4

dp 배열에는 i보다 이전의 인덱스에 위치한 숫자들 중에서 numbers[i]보다 작은 숫자들의 개수가 들어있다. i보다 이전의 인덱스에 위치한 숫자들 중에서 numbers[i]보다 작은 숫자 중 가장 큰 dp 값을 가진 숫자를 찾아서 1을 더해주면 현재 인덱스의 dp 값이 된다.

  • i = 0
    • 10보다 작은 max 숫자는 0 (0) -> 1
  • i = 1
    • 20보다 작은 max 숫자는 10 (1) -> 2
  • i = 3
  • 10보다 작은 max 숫자는 0 (0) -> 1
  • i = 4
    • 30보다 작은 max 숫자는 20 (2) -> 3

가장 긴 감소 부분 수열

가장 긴 증가 수열 문제에서 i보다 이전의 인덱스에 위치한 숫자들 중에서 numbers[i]보다 작은 숫자들의 개수를 계산했다면, 가장 긴 감소 수열 문제에서는 반대로 numbers[i]보다 큰 숫자들의 개수를 계산하면 된다.

첫번째 풀이

@Test
public void test() {
    assertThat(solution(1, "1"))
        .isEqualTo(1);
    assertThat(solution(10, "1 5 2 1 4 3 4 5 2 1"))
        .isEqualTo(7);
    assertThat(solution(7, "10 5 10 20 10 30 5"))
            .isEqualTo(5);
}

private int solution(int n, String numbers) {
    BitonicSubSequence biTonicSubNumbers = new BitonicSubSequence(n, numbers);
    return biTonicSubNumbers.maxLength();
}

static class BitonicSubSequence {

    private static final int MAX_LENGTH = 1000;
    private static final int PREV_SMALLER = 0;
    private static final int NEXT_SMALLER = 1;

    private final int n;
    private final int[] numbers;

    private int[][] dp;

    public BitonicSubSequence(int n, String numbers) {
        this.n = n;
        this.numbers = new int[n + 2];
        this.dp = new int[2][MAX_LENGTH + 1];

        StringTokenizer tokenizer = new StringTokenizer(numbers);
        for (int i = 1; i <= n; i++) {
            this.numbers[i] = Integer.parseInt(tokenizer.nextToken());
        }
    }

    public int maxLength() {
        int result = Integer.MIN_VALUE;

        for (int i = 1; i <= n; i++) {
            dp[PREV_SMALLER][i] = maxLengthPrevSmallerNumbers(i) + 1;
        }

        for (int i = n; i >= 1; i--) {
            dp[NEXT_SMALLER][i] = maxLengthNextSmallerNumbers(i) + 1;
            result = Math.max(result, dp[NEXT_SMALLER][i] + dp[PREV_SMALLER][i] - 1);
        }

        return result;
    }

    private int maxLengthNextSmallerNumbers(int i) {
        int result = 0;
        for (int j = i + 1; j <= n; j++) {
            result = max(result, i, j, NEXT_SMALLER);
        }
        return result;
    }

    private int maxLengthPrevSmallerNumbers(int i) {
        int result = 0;
        for (int j = i - 1; j >= 1; j--) {
            result = max(result, i, j, PREV_SMALLER);
        }
        return result;
    }

    private int max(int result, int i, int j, int SMALLER_INDEX) {
        if (this.numbers[i] > this.numbers[j]) {
            return Math.max(result, dp[SMALLER_INDEX][j]);
        }
        return result;
    }
}

가장 긴 증가 부분 수열을 앞 뒤로 계산하면 가장 긴 바이토닉 수열의 길이를 구할 수 있다.

i 0 1 2 3 4 5 6 7
numbers 0 10 5 10 20 10 30 5
dp[앞] 0 1 1 2 3 2 4 1
i 8 7 6 5 4 3 2 1
numbers 0 5 30 10 20 10 5 10
dp[뒤] 0 1 2 2 3 2 1 2

여기서 가장 긴 바이토닉 수열의 길이를 구하는 방법은 i를 기준으로 두 수열을 이어 붙이면 된다. 이어 붙이고 난 뒤에 수열에서 numbers[i]는 중복되므로 한번 제거해야 한다.

  • i = 4, numbers[i] = 20
    • dp[앞] + dp[뒤] - 1 = 3 + 3 - 1 = 5
    • 5 10 20 10 5
  • i = 6, numbers[i] = 30
    • dp[앞] + dp[뒤] - 1 = 4 + 2 - 1 = 5
    • 5 10 20 30 5

두번째 풀이

dp[앞], dp[뒤]를 계산하는 메소드의 코드에 많은 중복이 있다. 사실상 for 구문의 반복식을 세우는 부분을 제외하고는 완전 똑같다. 이 중복을 제거해보자.

private int maxLengthNextSmallerNumbers(int i) {
    return IntStream.rangeClosed(i + 1, n)
            .map(j -> max(i, j, NEXT_SMALLER))
            .max()
            .orElse(0);
}

private int maxLengthPrevSmallerNumbers(int i) {
    return IntStream.rangeClosed(1, i - 1)
            .map(j -> max(i, j, PREV_SMALLER))
            .max()
            .orElse(0);
}

private int max(int i, int j, int SMALLER_INDEX) {
    if (this.numbers[i] > this.numbers[j]) {
        return dp[SMALLER_INDEX][j];
    }
    return 0;
}

for문을 Stream API로 변경했을 뿐, 아직 중복되는 코드가 많다.

private int maxLengthNextSmallerNumbers(int i) {
    return maxRangeClosed(i + 1, n, i, NEXT_SMALLER);
}

private int maxLengthPrevSmallerNumbers(int i) {
    return maxRangeClosed(1, i - 1, i, PREV_SMALLER);
}

private int maxRangeClosed(int start, int end, int i, int SMALLER_INDEX) {
    return IntStream.rangeClosed(start, end)
        .map(j -> max(i, j, SMALLER_INDEX))
        .max()
        .orElse(0);
}

private int max(int i, int j, int SMALLER_INDEX) {
    if (this.numbers[i] > this.numbers[j]) {
        return dp[SMALLER_INDEX][j];
    }
    return 0;
}

이제 어느 정도 중복이 제거된 것 같다. maxRangeClosed의 인자 개수를 줄일 수 있다면 더 좋을 것 같다. 우선은 여기까지만..