[Swift] BOJ 2352 반도체 설계

BOJ 2352 반도체 설계

 

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

 

 

샘플 코드

        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
        }