Swift ) BOJ- 11053 가장 긴 증가하는 부분 수열(Lower Bound)

www.acmicpc.net/problem/11053

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

 

안녕하세요. 후르륵짭짭 입니다.

알고리즘은 참,,,, 쉽지 않습니다.

예전에 푼 문제인데,,,, 오랜만에 풀려고 하니 못 풀었네요 ㅎㅎㅎㅎ.

일단 저는 이 문제를 Lower Bound로 풀었습니다.

 

** 정답 코드 **

import Foundation

let N = Int(readLine()!)!

let list = readLine()?.components(separatedBy: " ").map({ item -> Int in
    return Int(item)!
})

func getLowerBound(_ find : Int ,_ containList : [Int]) -> Int{
    
    var start = 0
    var end = containList.count - 1
    var mid = (start + end) / 2
    
    while start < end {
        
         mid = (start + end) / 2
        
        if containList[mid] < find {

            start = mid + 1
        }
        else {

            end = mid
            
        }
        
    }
    
    return end
    
}


func solution() -> Int{
     
    
    var containList : [Int] = []
    
    for item in list! {
        
        if containList.isEmpty {
            containList.append(item)
        }
        else {
            
            if containList[containList.count - 1] < item {
                    containList.append(item)
            }
            else {
                
                let location = getLowerBound(item, containList)
                
                containList[location] = item

            }
            
        }
        
    }
    
    return containList.count
}

print(solution())

 

** 시행착오 **

import Foundation

let N = Int(readLine()!)!

let list = readLine()?.components(separatedBy: " ").map({ item -> Int in
    return Int(item)!
})

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


func solution() -> Int{
     
    
    var containList : [Int] = []
    
    for item in list! {
        //print(containList)
        if containList.isEmpty {
            containList.append(item)
        }
        else {
            
            if containList[containList.count - 1] < item {
                    containList.append(item)
            }
            else {
                
                let location = getLowerBound(item, containList)
                
                if location < containList.count{
                
                    for index in (location...containList.count-1).reversed(){
                        containList.remove(at: index)
                    }
                    
                    containList.append(item)
                        
                }
            
                
            }
            
        }
        
    }
    
    return containList.count
}

print(solution())

처음에는 이렇게 코드를 작성했습니다.

일단 둘의 큰 차이는 딱 봐도 두 함수 모두 존재합니다.

처음에 생각한 방식은

10 20 10 30 20 50

이라 할때,

10 -> 10 20 -> 10 20 -> 10 20 30 -> 10 20 30 -> 10 20 30 50 

이렇게 해서 4가 나왔습니다.

                if location < containList.count{
                
                    for index in (location...containList.count-1).reversed(){
                        containList.remove(at: index)
                    }
                    
                    containList.append(item)
                        
                }

 

이 부분은 2가지의 특징이 있습니다.

   1) 같은 숫자가 존재하면 넣어주지 않고 넘어간다.

   2) 새로운 작은 숫자가 들어가면 새롭게 만들어줘야 하기때문에 그 이후의 숫자는 지워버린다.

아주 잘못 된 생각 이였습니다 ㅎㅎㅎㅎㅎ.

 

왜 안 될까 생각해보니,

만약에 10 20 50 70  30 40

이럴 경우는 10 20 50 70 과 10 20 30 40 모두  4라서 같습니다.

그런데 만약 10 20 50 70  30 

이렇다고 할 때, 10 20 30 과 10 20 50 70 이 됩니다.

50을 30으로 바꿔도 최장 길이는 10 20 50 70 입니다. 따라서 다 이후의 숫자를 지워주면 최장의 숫자를 지울 수 있게 되는 겁니다.

그래서 그 후에 것들을 지우면 안되는 거였습니다.

 

이렇게 되면 이제 Lower Bound도 수정해줘야합니다.

왜냐하면 현재 찾은 부분은 위치를 알려주고 

없을 때

 1) 맨 첫 번째 위치 보다 작은 숫자 인데 존재하지 않을 때는 0을 반환해주고

 2) 맨 첫 번째 위치 보단 크지만 존재 하지 않을 때는 가장 가까운 숫자 위치 + 1 을 해줘야 한다.

이것을 어떻게 할 지 고민하다가 결국 

blog.naver.com/PostView.nhn?blogId=bestmaker0290&logNo=220820005454

알고리즘 기초 - Lower Bound & Upper Bound

여기를 통해 참조하게 되었다.

 

여기에서의 Lower Bound와 내것의 차이는 매우 크지만

나는 반환을 mid로 하고 정답은 end를 반환하게 된다.

왜 end 일지 생각을 해보니

end가 끝 부분을 나타내기 때문이다.

 

아,,, 알고리즘,,,,, 내 스타일은 아니지만,,, 해야하니 어쩔 수 없이 한다.