문제
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.
입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다.
둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000)
출력
첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.
둘째 줄에는 정답이 될 수 있는 가장 긴 증가하는 부분 수열을 출력한다.
내가 푼 풀이
이제까지 가장 긴 증가하는 부분수열(LIS)를 구하는 방법은 두가지가 있었다.
첫번째는 DP방법으로 해당 인덱스의 원소까지의 부분수열 길이를 최신화 하는 방법이였다.
이는 시간복잡도가 O(N2)가 걸리므로 주어진 문제의 입력은 최대 100만개의 원소이므로 시간초과가 일어났다.
두번째 방법으론 이분탐색이 있다.
이분탐색을 통해 이문제를 해결했지만 몇가지 주의해야할 점이 있었다.
이전에 이분탐색으로 구하면 최장증가 부분수열의 "길이"만 구할 수 있었다.
이분탐색을 통해 배열에서 원소가 위치하는 자리를 구하고 해당위치에 넣은결과 길이는 정답이지만, 부분수열이 옳지 않게 구하게 되었다.
예로 수열 [10, 20, 10, 30, 15, 50]이 주어졌을 때, 이분탐색을 이용하여 구한다면
[10, 15, 30, 50]배열이 구해지고 이는 최장증가 부분수열이 아니다.
이유는 15는 50이전의 원소로 30보다 나중에 나오는 원소이므로 옳지 않다.
부분수열은 구할 수 없지만 길이는 알고있다.
이 점을 이용하여 이분탐색을 통해 부분수열을 구할 때, 해당 원소의 인덱스를 저장한다.
괄호안 숫자는 해당원소가 주어진 수열의위치를 의미한다.
첫번째 원소 10
첫번째 원소는 비교대상이 없으므로 첫번째에 넣는다.
result = [10(1)]
idx = [1]
두번째 원소 20
두번쨰 원소는 이분탐색을 이용하여 10뒤에 오는 숫자임을 알 수 있다.
result = [10(1), 20(2)]
idx = [1, 2]
세번째 원소 10
세번째 원소는 이분탐색 결과 첫번째 오는 숫자와 같음을 알 수 있다.
result = [10(3), 20(2)]
idx = [1, 2, 1]
네번째 원소 30
네번째 원소는 20뒤에오는 숫자임을 알 수 있다.
result = [10(3), 20(2), 30(4)]
idx = [1, 2, 1, 3]
다섯번째 원소 15
다섯번째 원소는 이분탐색 결과 10과 20사이에 오는 숫자임을 알 수 있다.
이분탐색 결과 부분수열은 아래와 같다.
result = [10(3), 15(5), 30(4)]
idx = [1, 2, 1, 3, 2]
-> 이분탐색으로 만들어진 부분수열은 이미 정답과는 다른 부분수열이 만들어졌다. 해당원소의 위치를 배열안에 저장한다.
여섯번째 원소 50
여섯번째 원소는 이분탐색결과 마지막에 오는 숫자임을 알 수 있다.
result = [10(3), 15(5), 30(4), 50(6)]
idx = [1, 2, 1, 3, 2, 4]
-> 결과
result = [10(3), 15(5), 30(4), 50(6)]
idx = [1, 2, 1, 3, 2, 4]
이전의 이분탐색을 이용하면 result 배열을 얻고 길이는 정답이지만 부분 수열은 옳지않은 수열이 된다.
이분탐색을 통해 부분수열의 값이 변경될때 해당 원소가 위치하는 인덱스값을 저장함으로써 길이를 차감하며 부분수열을 구할 수 있게된다.
길이가 4이므로 역순으로 4 3 2 1의 원소를 뽑으면 [50, 30, 20 ,10]이고 이배열의 역순은 정답이 된다.
이분탐색을 이용하는 방법은 알았지만, 부분수열을 뽑아내는 과정은 쉽게 떠올리지 못했다.
코드로 구현하면 다음과 같다.
import Foundation
// 입력받기
let N = Int(readLine()!)!
var A = readLine()!.split(separator: " ").map{Int(String($0))!}
A.insert(0, at: 0)
let INF = 1000000001
// 이분탐색 결과배열과 인덱스 배열
var result = Array(repeating: INF, count: N+1)
var idxArr = [Int]()
result[1] = A[1]
// 이분탐색
func binarySearch(num: Int) {
var left = 1
var right = result.count-1
while left <= right {
let mid = (right + left) / 2
if result[mid] < num {
left = mid + 1
} else {
right = mid - 1
}
}
// 해당위치에 넣고, 인덱스배열에 저장
result[left] = num
idxArr.append(left)
}
for i in 1...N {
binarySearch(num: A[i])
}
var answer = [Int]()
var count = 0
// 부분수열의 길이 구하기
for i in 1...N {
if result[i] != INF {
count += 1
} else {
break
}
}
// 부분수열 구하기
for i in (0..<idxArr.count).reversed() {
if idxArr[i] == count {
count -= 1
answer.append(A[i+1])
}
}
// 출력
print(answer.count)
print(answer.map{String($0)}.reversed().joined(separator: " "))
'코딩테스트 > 백준' 카테고리의 다른 글
| BOJ-17404 RGB거리 2 Swift (1) | 2024.07.16 |
|---|---|
| BOJ-2631 줄세우기 Swift (0) | 2024.06.17 |
| BOJ-1450 냅색문제 Swift (0) | 2024.06.06 |
| BOJ-1644 소수의 연속합 Swift (0) | 2024.06.06 |
| BOJ-11657 타임머신 Swift (1) | 2024.06.04 |
