[Swift] BOJ 2352 반도체 설계

BOJ 2352 반도체 설계

 

✅ 이 문제는 아래 문제 코드와 아예 똑같다..

근데 하나 다른 점이라면 풀이를 떠올리기가 훨씬 더 어려웠다는 점.

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

 

[문제 설명]

꼬이지 않는다라는 말이 이해가 가지 않았는데, 연결 선이 서로 겹쳐지지 않는다는 말임결국은 증가하는 부분수열 처럼 되는 문제임. 

 

 

 

 

✅ 코드

        let _ = Int(readLine()!)!
        let input = readLine()!.split(separator: " ").map { Int($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)
        }
        print(list.count)
        
        
        func lowerBound(arr: [Int], n: Int, key: Int) -> 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
        }