BOJ-11054 가장 긴 바이토닉 부분수열 Swift

 

문제

수열 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가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

내가 푼 풀이

- 수열이 주어졌을 때, 각 위치 인덱스에서 만들 수 있는 바이토닉 수열의 길이 최댓값을 출력한다.

- dp[i] = j : i번째 인덱스의 원소값을 기준으로 했을 때의 증가하는 수열의 길이

- rdp[i] = j : i번째 인덱스의 원소값을 기준으로 i+1 이후로 감소하는 수열의 길이

 

예시

arr = [1,2,1,5]

- index = 0인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[0] = 1

arr	0	1	2	3
dp	1

- index = 1인 원소 2가 주어졌을 때, 2 자체로 수열의 길이 1을 가진다. dp[1] = 1

- arr[0] = 1은 2보다 작은 값이다.

- 인덱스 1 이전의 원소중 중복되는 작은 수가 없다. 

- dp[1] = dp[1] + 1

arr	1	2	1	5
dp	1	2

- index = 2인 원소 1이 주어졌을 때, 1 자체로 수열의 길이 1을 가진다. dp[2] = 1

- arr[0] = 1은 같은 값이므로 패스한다.

- arr[1] = 2는 큰 값이므로 패스한다.

- 인덱스 2 이전의 원소중 작은 값이 없다.

arr	1	2	1	5
dp	1	2	1

- index = 3인 원소 5가 주어졌을 때, 5 자체로 수열의 길이 1을 가진다. dp[3] = 1

- arr[0] = 1은 5보다 작은 값이다.

- 0번째 인덱스 이전의 값이 없으므로 dp[3] = dp[3] + 1 (dp[3] = 2)

- arr[1] = 2는 5보다 작은 값이다.

- 1번째 인덱스 이전의 값 중 2와 중복된 수가 없으므로 dp[3] = dp[3] + 1 (dp[3] = 3)

- arr[2] = 1은 5보다 작은 값이다.

- 2번째 인덱스 이전의 값 중 = arr[2] 이므로 중복된 수로 dp값을 증가시키지 않는다.

arr	1	2	1	5
dp	1	2	1	3

 

위 예시를 통해 조건을 다음과 같이 구현할 수 있다.

1. 이전 인덱스의 원소보다 큰가?

2. 이전 인덱스의 작은 원소들 중 중복되지 않는가?

dp[i] = j 라 했을 때, i번째 원소를 기준으로 증가하는 수열의 길이를 넣었으므로

중복되는지 체크하려면, dp[j] + 1 > dp[i] 이어야 한다.

위 예시에서 arr[3] = 5에서 확인할 때, 0번째 인덱스에서 이미 dp값을 증가시켰으므로 5를 기준으로 한 증가수열에 이미 1이 들어가 있다.

그러고 2번째에서 다시 1을 만났을 때, 이미 중복되므로 dp값을 증가시키지 않았다.

 

바이토닉수열은 어떤 수 기준으로 증가수열과 감수수열을 합친 것이므로, 위 순서를 역순으로 하면 감소하는 수열이 나온다.

증가수열 + 감소수열을 해준 후, 이는 기준이 되는 수가 중복으로 들어가 있으므로 -1을 해주고 결과 중 최댓값을 출력한다.

import Foundation

let count = Int(readLine()!)!
var arr = readLine()!.split(separator: " ").map{ Int($0)! }
var dp = Array(repeating: 0, count: count)
var rdp = Array(repeating: 0, count: count)

// 각 위치의 원소는 그 원소 하나 자체로 바이토닉 수열의 길이 1을 가진다.
// 인덱스 하나를 기준으로 이전 인덱스의 원소들을 모두 검사한다.
// 이전 원소보다 크고, 작은 원소가 중복되지않는 경우 1을 추가해준다.
for i in 0..<dp.count {
    dp[i] = 1
    for j in 0..<i {
        if arr[i] > arr[j] && dp[i] < dp[j] + 1 {
            dp[i] += 1
        }
    }
}

// 위 dp는 증가하는 수열의 길이를 구했다면, rdp는 감소하는 수열의 길이를 구하는것이다.
for i in (0..<rdp.count).reversed() {
    rdp[i] = 1
    for j in (i..<rdp.count).reversed() {
        if arr[i] > arr[j] && rdp[i] < rdp[j] + 1 {
            rdp[i] += 1
        }
    }
}

// 한 원소를 기준으로 했을때, dp rdp를 모두 구하고 더하면 기준이되는 원소가 중복으로 더해지므로 -1을 해준다.
for i in 0..<dp.count {
    dp[i] += rdp[i] - 1
}
print(dp.max()!)