[Swift 알고리즘] 백준 1377 버블소트

 

https://www.acmicpc.net/problem/1377

 

 

 

해결방법 : 정렬전과 정렬 후의 arrInd를 확인하여 푼다.

버블소트로 정렬하면 시간초과~

func sol1377() {
    let inputN = Int(readLine()!)!
    var targetArr = Array(repeating: 0, count: inputN)
    for i in 0..<inputN {
        targetArr[i] = Int(readLine()!)!
    }
    var changed = false
    for i in 0..<inputN {
        changed = false
        for j in 0..<inputN - i - 1 {
            if targetArr[j] >= targetArr[j + 1] {
                targetArr.swapAt(j, j + 1)
                changed = true
            }
        }
        if changed == false {
            print(i + 1)
            break
        }
    }
    
}

sol1377()

 

 

 

 

func sol1377() {
    let inputN = Int(readLine()!)!
    var targetArr = Array(repeating: [0], count: inputN)
    for i in 0..<inputN {
        targetArr[i] = [Int(readLine()!)!, i]
    }
    var tempArr = targetArr.sorted{tm1, tm2 in
        return tm1[0] < tm2[0]
    }
    var solarr = Array(repeating: 0, count: inputN)
    for i in 0..<inputN {
        solarr[i] = tempArr[i][1] - i
    }
    print(solarr.max()! + 1)
    
}

sol1377()