[Swift 알고리즘] 백준 BOJ - 12015 가장 긴 증가하는 부분 수열2

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "백준 BOJ - 12015 가장 긴 증가하는 부분 수열2" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

12015번: 가장 긴 증가하는 부분 수열 2

 

---

풀이

이번 문제는 DP 문제로 LIS 유형입니다.

이전 문제와는 다르게 O(N^2)으로는 풀 수 없는 문제로 lower bound라는 이진탐색 O(N log N) 방법을 이용해야 합니다.

lower bound란, 입력 n과 배열이 있을 때 n 이상이 나타나는 처음의 index를 구하는 방법입니다.

 

이번 문제는 두 가지 시나리오로 나눌 수 있습니다.

부분 수열을 오름차순으로 저장하는 배열 A가 있을 때

1. A의 맨 뒤에 넣을 수 있는 경우
2. A 중간 혹은 처음에 넣어야 하는 경우

1번은 맨 뒤 숫자와 기준 number를 비교해서 number가 더 크면 맨 뒤에 넣을 수 있습니다.

 

2번 시나리오에서 lower bound를 이용합니다.

배열 A에 [2 4 5 6]이 있고 1을 넣어야 한다면 lower bound를 통해 1이라는 index를 얻을 수 있고 그 index의 값을 1로(정확히는 더 작은 값으로) 업데이트 합니다.

 

이렇게 삽입과 업데이트를 모든 number에 대해 완료 했다면 배열 A의 길이가 가장 긴 증가하는 부분 수열의 길이입니다.

 

---

전체 코드

//12015 가장 긴 증가하는 부분 수열2
import Foundation

func lowerBound(find: Int, numbers: [Int]) -> Int {
    var start = 0, end = numbers.count - 1
    var mid = (start + end) / 2
    
    while start < end {
        mid = (start + end) / 2
        if numbers[mid] < find {
            start = mid + 1
        } else {
            end = mid
        }
    }
    
    return end
}

let input = Int(readLine()!)!

var numbers: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

var dp: [Int] = []
for number in numbers {
    if dp.isEmpty {
        dp.append(number)
        continue
    }
    
    if dp[dp.count - 1] < number {
        dp.append(number)
    } else {
        let index = lowerBound(find: number, numbers: dp)
        dp[index] = number
    }
}

print(dp.count)

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.