백준 - 줄 세우기(Swift)

백준 - 줄 세우기(Swift)

 

 

 문제 설명

 

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

10431번: 줄세우기

 

 나의 풀이

 

들어갈 인덱스를 찾아서 삽입해주면 되는 문제다.

처음에는 버블정렬과 같이 계속해서 값을 swap하는 형식으로 구현했었는데 인덱스를 찾아서 삽입하는게 더욱 직관적이라는 생각이 들어서 아래와 같이 구현했다.

 

import Foundation

let tc = Int(readLine()!)!

for t in 0..<tc {
    let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
    let num = arr[0]
    var sortedArr = [arr[1]]
    var cnt = 0
    for i in 2..<arr.count {
        var insertIndex = sortedArr.count
        for j in stride(from: sortedArr.count-1, to: -1, by: -1) {
            if arr[i] > sortedArr[j] {
                break
            } else {
                insertIndex -= 1
                cnt += 1
            }
        }
        sortedArr.insert(arr[i], at: insertIndex)
    }
    print("\(t+1) \(cnt)")
}