백준_숫자만들기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)
Author And Source
이 문제에 관하여(백준_숫자만들기2_오답), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kyustudyo/백준숫자만들기2오답저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)