[Swift] BOJ 12738 가장 긴 증가하는 부분 수열 3

BOJ 12738 가장 긴 증가하는 부분 수열 3 

 

✅ 풀었다.

 

일단 이 문제는 dp를 사용해서 풀려고 했었는데, 시간 초과로 다른 접근 방법이 필요했다.

2022.04.01 - [코딩테스트] - [Swift] BOJ 11053 가장 긴 증가하는 부분 수열

[Swift] BOJ 11053 가장 긴 증가하는 부분 수열

위의 문제는 dp로 해결이 가능했었는데

 

아무튼 아이디어가 도통 떠오르지 않아서 다른 분들의 로직을 참고하였음.

 

✅ 알고리즘 접근법

이분 탐색을 이용하였는데, C++에는 lower_bound를 제공해주어서 그런지, 이 부분을 따로 구현하지 않더라.

진짜 Swift로 알고리즘 공부하는데 가장 힘든 것은 직접 전부 구현해야 하는 것들이 정말 많다는 것이다.

 

 

1. list의 마지막 값과 현재 값을 비교.

2.  

  2-1. 현재 값이 list의 마지막 값보다 크다면 list의 끝에 현재 값을 대입 

  2-2. 현재 값이 list의 마지막 값보다 작다면 list를 거꾸로 순회       

    2-2-1. lowerBound를 통해서 나보다 작은 값의 index를 찾음. 

  2-3. lowerBound를 통해 찾은 list[index]를 현재 값으로 변경

 

여기서 잘 이해해야 하는 포인트는 어차피 list의 길이가 최대 길이라는 점이지 그 안의 원소를 하나하나 따질 필요가 없다.

 

 

 

✅ 코드

        let _ = Double(readLine()!)!
        let input = readLine()!.components(separatedBy: " ").map{ Double($0)! }
        
        // 최장 수열을 담을 배열이 필요하다.
        var list = [input[0]]
        
        /* (로직)
            값이 있는 부분의 뒤에서부터 탐색한다.
            탐색하려는 인덱스의 값보다 새로운 값이 더 큰 경우에는 탐색하려는 인덱스 뒤에 값을 넣어줍니다.
            탐색 인덱스가 맨 처음 인덱스까지 가도 자신보다 작은 인덱스를 못찾는 경우 맨 처음에 넣어준다.
            항생 배열에 들아간 숫자의 갯수가 최장 수열의 길이이다.
         */
        input.forEach { element in
            if element == list.last { }
            else if element > list.last! {
                list.append(element)
            } else { // 이 경우에는 list순회
                let position = lowerBound(arr: list, n: list.count, key: element)
                list[position] = element
            }
        }
        print(list.count)
        
        
        func lowerBound(arr: [Double], n: Int, key: Double) -> Int {
            var start: Int = 0
            var end: Int = n
            
            var mid: Int = n
            
            while end - start > 0 {
                mid = (start + end) / 2
                
                if arr[mid] < key {
                    start = mid + 1
                } else {
                    end = mid
                }
            }
            return end
        }

 

 

(참고)

http://melonicedlatte.com/algorithm/2018/07/15/171956.html

[백준] 12738번 C/C++ 풀이 _ 가장 긴 증가하는 수열 3 - Easy is Perfect

https://kunkunwoo.tistory.com/157

백준 12738번, 14003번 _ 가장 긴 증가하는 부분 수열 3, 5

https://blockdmask.tistory.com/168

[탐색] lower_bound, upper_bound

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기