백준_숫자만들기2_오답

시간복잡도 O(n log(n)) 인것같은데 시간초과이다.
다른 분들 대부분 dictionary로 풀었다. 그렇게 해야겠다.

import Foundation
var firstN = Int(readLine()!)
var firstArray = readLine()!.split(separator: " ").map{Int($0)!}
var secondN = Int(readLine()!)
var secondArray = readLine()!.split(separator: " ").map{Int($0)!}
var lastIndex = firstArray.count - 1

var result = [Int]()
var testResult = 0
func findN(Arr:[Int],startIndex:Int,endIndex:Int,targetN:Int)->Int{
    var nextStartIndex = startIndex
    var nextEndIndex = endIndex
    if startIndex > endIndex { return -1}
   
    let mid = (startIndex + endIndex)/2
//    print("nebo",targetN,startIndex,endIndex,mid)
    if Arr[mid] == targetN {
        if mid != 0 {
            if Arr[mid-1] == targetN {
                nextStartIndex = startIndex
                nextEndIndex = mid - 1
                return findN(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
            }
        }
    return mid
        
    }
    
    else if Arr[mid] < targetN { nextStartIndex = mid + 1}
    else if Arr[mid] > targetN { nextEndIndex = mid - 1}
    return findN(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
}
func findM(Arr:[Int],startIndex:Int,endIndex:Int,targetN:Int)->Int{
    var nextStartIndex = startIndex
    var nextEndIndex = endIndex
    //print("s,e",startIndex,endIndex)
    if startIndex > endIndex {
        //print("ww")
        return -1
        
    }
   
    let mid = (startIndex + endIndex)/2
    //print("general m",mid)
//    print("nebo",targetN,startIndex,endIndex,mid)
    if Arr[mid] == targetN {
        //print("specail:",mid)
        if mid != lastIndex {
            if Arr[mid+1] == targetN {
                //print("not end",mid)
                nextStartIndex = mid + 1
                nextEndIndex = endIndex
                //print("end",nextEndIndex)
                return findM(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
            }
        }
        //print("return mid")
    return mid
        
    }
    
    else if Arr[mid] < targetN {
        //print("target 크다")
        nextStartIndex = mid + 1
        
    }
    else if Arr[mid] > targetN {
        //print("target 작다")
        nextEndIndex = mid - 1
        
    }
    return findM(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
}

var sortedArray = firstArray.sorted{$0<$1}
for n in secondArray {
//    print("시작:\(n)")
    let N = findN(Arr: sortedArray, startIndex: 0, endIndex: lastIndex, targetN: n)
    let M = findM(Arr: sortedArray, startIndex: 0, endIndex: lastIndex, targetN: n)
    //print(sortedArray,lastIndex,n,N)
    if N == -1 || M == -1 {
        print(0, terminator: " ")
        //result.append(0)
    }
    else{
        print(M - N + 1, terminator: " ")
        //result.append(M - N + 1)
    }
    
    //print(N,M)
    
}

확인결과
n log(n)은 맞으나 swift에서 print와 readline 이 느리다고한다. 따라서 다음과 같이 빠른 입출력을 이용해서 정답을 맞았다. 알고리즘은 맞은것이었다.

import Foundation

final class FileIO {
    private let buffer:[UInt8]
    private var index: Int = 0

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        
        buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer[index]
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() } // 공백과 줄바꿈 무시
        if now == 45 { isPositive.toggle(); now = read() } // 음수 처리
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return String(bytes: Array(buffer[beginIndex..<(index-1)]), encoding: .ascii)!
    }

    @inline(__always) func readByteSequenceWithoutSpaceAndLineFeed() -> [UInt8] {
        var now = read()

        while now == 10 || now == 32 { now = read() } // 공백과 줄바꿈 무시
        let beginIndex = index-1

        while now != 10,
              now != 32,
              now != 0 { now = read() }

        return Array(buffer[beginIndex..<(index-1)])
    }
}
let FIO = FileIO()

var firstN = FIO.readInt()
var firstArray: [Int] = []
for _ in 0..<firstN {
    firstArray.append(FIO.readInt())
}

var secondN = FIO.readInt()
var secondArray: [Int] = []
for _ in 0..<secondN {
    secondArray.append(FIO.readInt())
}

var lastIndex = firstArray.count - 1

var result = [Int]()
var testResult = 0
func findN(Arr:[Int],startIndex:Int,endIndex:Int,targetN:Int)->Int{
    var nextStartIndex = startIndex
    var nextEndIndex = endIndex
    if startIndex > endIndex { return -1}
   
    let mid = (startIndex + endIndex)/2
//    print("nebo",targetN,startIndex,endIndex,mid)
    if Arr[mid] == targetN {
        if mid != 0 {
            if Arr[mid-1] == targetN {
                nextStartIndex = startIndex
                nextEndIndex = mid - 1
                return findN(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
            }
        }
    return mid
        
    }
    
    else if Arr[mid] < targetN { nextStartIndex = mid + 1}
    else if Arr[mid] > targetN { nextEndIndex = mid - 1}
    return findN(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
}
func findM(Arr:[Int],startIndex:Int,endIndex:Int,targetN:Int)->Int{
    var nextStartIndex = startIndex
    var nextEndIndex = endIndex
    //print("s,e",startIndex,endIndex)
    if startIndex > endIndex {
        //print("ww")
        return -1
        
    }
   
    let mid = (startIndex + endIndex)/2
    //print("general m",mid)
//    print("nebo",targetN,startIndex,endIndex,mid)
    if Arr[mid] == targetN {
        //print("specail:",mid)
        if mid != lastIndex {
            if Arr[mid+1] == targetN {
                //print("not end",mid)
                nextStartIndex = mid + 1
                nextEndIndex = endIndex
                //print("end",nextEndIndex)
                return findM(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
            }
        }
        //print("return mid")
    return mid
        
    }
    
    else if Arr[mid] < targetN {
        //print("target 크다")
        nextStartIndex = mid + 1
        
    }
    else if Arr[mid] > targetN {
        //print("target 작다")
        nextEndIndex = mid - 1
        
    }
    return findM(Arr: Arr, startIndex: nextStartIndex, endIndex: nextEndIndex, targetN: targetN)
}

var sortedArray = firstArray.sorted{$0<$1}


var output = ""
for n in secondArray {
    let N = findN(Arr: sortedArray, startIndex: 0, endIndex: lastIndex, targetN: n)
    let M = findM(Arr: sortedArray, startIndex: 0, endIndex: lastIndex, targetN: n)
        
    if N == -1 || M == -1 {
        output += "0 "
    }
    else{
        output += "\(M - N + 1) "
    }
}

print(output)