Swift 백준 10816번) 숫자 카드 2 (삽질..)

OdSmith 2022. 8. 31. 20:27

2022. 8. 31. 20:27

숫자 카드 2

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

79732

29195

20956

35.904%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1 복사

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 1 복사

3 0 0 1 2 0 0 2

출처

문제를 만든 사람: baekjoon
문제의 오타를 찾은 사람: cko301, mwy3055, wkd48632
데이터를 추가한 사람: emppu, jh05013

알고리즘 분류

실패코드 1트

func sequencial(_ array: [Int], num: Int) -> Int {
    var a = 0
    for element in array {
        if num == element {
            a += 1
        }
    }
    return a
}


var N = Int(readLine()!)!
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
var M = Int(readLine()!)!
let input_M = readLine()!.split(separator: " ").map{Int(String($0))!}

input_N.sort()

var arr = [Int]()
for i in 0..<M{
    arr.append(sequencial(input_N, num: input_M[i]))
}
print(arr.map{String($0)}.joined(separator: " "))

이진탐색으로 어떻게 해야할지 잘모르겠어서 완전탐색으로 하였다..

-> 당연히 시간초과 ㅋㅋㅌ ㅆ,,

실패코드 2트

func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
    let mid = Int((left + right) / 2)
    var count = 0
    
    if target == input_N[mid]{
        var midLeft = mid - 1
        count += 1
        while midLeft >= 0 && target == input_N[midLeft]{
            count += 1
            midLeft -= 1
        }
        var midRight = mid + 1
        while midRight < input_N.count && target == input_N[midRight]{
            count += 1
            midRight += 1
        }
        return count
    }
    
    if left > right || target < input_N[left] || target > input_N[right]{
        return count
    }
    
    if target > input_N[mid]{
        return binarySearch(mid + 1, right, target)
    }else if target<input_N[mid]{
        return binarySearch(left, mid - 1, target)
    }
    return count
}

var N = Int(readLine()!)!
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}
var M = Int(readLine()!)!
let input_M = readLine()!.split(separator: " ").map{Int(String($0))!}

input_N.sort()

var arr : [Int] = []
for i in input_M{
    arr.append(binarySearch(0 , N-1 , i))
}
print(arr.map{String($0)}.joined(separator: " "))

나름 이분탐색 사용하였지만 다시나는 시간초과,,, 무엇이 문제일까..?

다음에 알아보도록 하자....

실패코드 3트

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)])
    }
}

func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
    let mid = Int((left + right) / 2)
    var count = 0
    
    if target == input_N[mid]{
        var midLeft = mid - 1
        count += 1
        while midLeft >= 0 && target == input_N[midLeft]{
            count += 1
            midLeft -= 1
        }
        var midRight = mid + 1
        while midRight < input_N.count && target == input_N[midRight]{
            count += 1
            midRight += 1
        }
        return count
    }
    if left > right || target < input_N[left] || target > input_N[right]{
        return count
    }
    if target > input_N[mid]{
        return binarySearch(mid + 1, right, target)
    }else if target<input_N[mid]{
        return binarySearch(left, mid - 1, target)
    }
    return count
}


let fileIO = FileIO()
var input_N: [Int] = []
var input_M: [Int] = []

let N = fileIO.readInt()
for _ in 0..<N {
    input_N.append(fileIO.readInt())
}

let M = fileIO.readInt()
for _ in 0..<M {
    input_M.append(fileIO.readInt())
}

input_N.sort(by: <)

var result = ""
for i in input_M{
    let count = binarySearch(0 , N-1 , i)
    result += "\(count) "
}
print(result)

시간..초,,ㄱ..ㅘ....

딱알았다.. sort때문인거같으 이것만 다시해서 올려보겠습니다..ㅎ

4트ㅎㅎ

//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)])
//    }
//}

func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
    let mid = Int((left + right) / 2)
    var count = 0
    
    if target == input_N[mid]{
        var midLeft = mid - 1
        count += 1
        while midLeft >= 0 && target == input_N[midLeft]{
            count += 1
            midLeft -= 1
        }
        var midRight = mid + 1
        while midRight < input_N.count && target == input_N[midRight]{
            count += 1
            midRight += 1
        }
        return count
    }
    if left > right || target < input_N[left] || target > input_N[right]{
        return count
    }
    if target > input_N[mid]{
        return binarySearch(mid + 1, right, target)
    }else if target<input_N[mid]{
        return binarySearch(left, mid - 1, target)
    }
    return count
}


func quickSort(numArr : [Int]) -> [Int]{
    if numArr.count < 2{
        return numArr
    }
    
    let pivot = numArr[0]
    var left :[Int] = []
    var right :[Int] = []
    
    
    for i in 1..<numArr.count{
        if pivot > numArr[i]{
            left.append(numArr[i])
        }else if pivot < numArr[i] {
            right.append(numArr[i])
        }else if pivot == numArr[i]{
            left.insert(numArr[i], at: 0)
        }
    }
    return quickSort(numArr: left) + [pivot] + quickSort(numArr: right)
}



//let fileIO = FileIO()
//var input_N: [Int] = []
//var input_M: [Int] = []

//let N = fileIO.readInt()
let N = Int(readLine()!)!

//for _ in 0..<N {
//    input_N.append(fileIO.readInt())
//}
var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}

//let M = fileIO.readInt()
let M = Int(readLine()!)!
//for _ in 0..<M {
//    input_M.append(fileIO.readInt())
//}
var input_M = readLine()!.split(separator: " ").map{Int(String($0))!}

input_N = quickSort(numArr: input_N)

var result = ""

for i in input_M{
    let count = binarySearch(0 , N-1 , i)
    result += "\(count) "
}
print(result)

sort를 퀵정렬로 바꿨는뎀 요것도 시간초과네요..? ㅎㅎ 아 주석은 디버깅때문에 해뒀습니다.

이렇게 해보니 1트와 2트는 그냥 틀린것 같네요? ㅎㅎ (말로만 1트 2트지 수많은 트라이들이...)

다른분들은 lower upper 나눠서 하길래 나는 다른길을 걷고자 악바리로 한번에 해보려했지만 안되는것같네요?ㅎㅎ

아직 의지는 꺾이지 않았습니다.

제출코드 5트..

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)])
    }
}

func lowerBound(_ left: inout Int,_ right: inout Int , _ target: Int) -> Int{
    while left < right{
        let mid = Int((left + right) / 2)
        if input_N[mid] < target {
            left = mid + 1
        }else if target <= input_N[mid] {
            right = mid
        }
    }
    return left
}

func upperBound(_ left: inout Int,_ right: inout Int , _ target: Int) -> Int{
    while left < right{
        let mid = Int((left + right) / 2)
        if input_N[mid] <= target{
            left = mid + 1
        }else if target < input_N[mid]{
            right = mid
        }
    }
    return right
}

func binarySearch(_ left: Int,_ right: Int , _ target: Int) -> Int{
    let mid = Int((left + right) / 2)
    var count = 0
    
    if target == input_N[mid]{
        var midLeft = mid - 1
        count += 1
        while midLeft >= 0 && target == input_N[midLeft]{
            count += 1
            midLeft -= 1
        }
        var midRight = mid + 1
        while midRight < input_N.count && target == input_N[midRight]{
            count += 1
            midRight += 1
        }
        return count
    }
    if left > right || target < input_N[left] || target > input_N[right]{
        return count
    }
    if target > input_N[mid]{
        return binarySearch(mid + 1, right, target)
    }else if target<input_N[mid]{
        return binarySearch(left, mid - 1, target)
    }
    return count
}


func quickSort(numArr : [Int]) -> [Int]{
    if numArr.count < 2{
        return numArr
    }
    
    let pivot = numArr[0]
    var left :[Int] = []
    var right :[Int] = []
    
    
    for i in 1..<numArr.count{
        if pivot > numArr[i]{
            left.append(numArr[i])
        }else if pivot < numArr[i] {
            right.append(numArr[i])
        }else if pivot == numArr[i]{
            left.insert(numArr[i], at: 0)
        }
    }
    return quickSort(numArr: left) + [pivot] + quickSort(numArr: right)
}




let fileIO = FileIO()
var input_N: [Int] = []
var input_M: [Int] = []

var N = fileIO.readInt()
//var N = Int(readLine()!)!

for _ in 0..<N {
    input_N.append(fileIO.readInt())
}
//var input_N = readLine()!.split(separator: " ").map{Int(String($0))!}

var M = fileIO.readInt()
//var M = Int(readLine()!)!
for _ in 0..<M {
    input_M.append(fileIO.readInt())
}
//var input_M = readLine()!.split(separator: " ").map{Int(String($0))!}

//input_N = quickSort(numArr: input_N)
input_N.sort()

var result = ""
var zero = 0
var N_real = N


for i in input_M{
    //let count = binarySearch(0 , N-1 , i)
    let up = upperBound(&zero, &N, i)
    zero = 0
    N = N_real
    let lo = lowerBound(&zero, &N, i)
    zero = 0
    N = N_real
    let count = up - lo
    //print(String((upperBound(&zero, &N, i)) - (lowerBound(&zero, &N, i))), terminator: " ")
    result += "\(count) "
}
print(result)

upper 랑 lower로 나누어서 하는걸로 타협을 보았고... 퀵정렬보다 sort()가 더 빠르다는것을 알았습니다..

lower과 upper의 함수를 쓸때 파라미터가 call by refference이므로 inout을 사용하여 0과 N을 다시넣어주었습니다..

이중탐색과 퀵정렬 함수는 사용하지 않았습니다! ㅎㅎ...

도움주신분

https://everycommit.tistory.com/33

10816번: 숫자 카드 2 - 이분 탐색(Lower Bound, Upper Bound)

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카..

coucougo.com

저작자표시

'iOS > 백준' 카테고리의 다른 글

Swift 백준 1874번) 스택 수열 (2)	2022.09.12
Swift 백준 2164번) 카드 2 (0)	2022.08.30
Swift 백준 11650번) 좌표 정렬하기 (0)	2022.08.22
Swift 백준 11050번) 이항계수 1 (0)	2022.08.16
Swift 백준 10866번) 덱 (0)	2022.08.15

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

Mabataki Developer