숫자 카드 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

출처

 

실패코드 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

카드2 성공

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 128 MB 58758 30371 24894 51.921%

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 500,000)이 주어진다.

출력

첫째 줄에 남게 되는 카드의 번호를 출력한다.

예제 입력 1 복사

6

예제 출력 1 복사

4

알고리즘 분류

실패코드

import Foundation

struct Queue<T>{
    private var elements = [T]()
    init(_ queue: [T]) {
            self.elements = queue
        }
    
    public mutating func push(_ element: T){
        self.elements.append(element)
    }
    
    public mutating func pop() -> T? {
        if self.elements.isEmpty{
            return ( -1 as! T)
        }else{
            let pop = self.elements.first
            self.elements.remove(at: 0)
            return pop
        }
    }
    
    public func empty() -> Bool {
        return self.elements.isEmpty
    }
    
    public var size: Int {
        return self.elements.count
    }
    
    public mutating func front() -> T? {
        if self.elements.isEmpty{
            return (-1 as! T)
        }else{
            return self.elements.first //맨앞정수
        }
    }
    public mutating func back() -> T? {
        if self.elements.isEmpty{
            return (-1 as! T)
        }else{
            return self.elements.last //맨뒤정수
        }
    }
}

let input = Int(readLine()!)!
var arr = [Int](1...input)
var myQueue = Queue<Int>(arr)


while myQueue.size != 1{
    myQueue.pop()!
    myQueue.push(myQueue.front()!)
    myQueue.pop()!
}
print(myQueue.pop()!)

while문 안쪽 과 큐 선언의 문제가 있어보여 다시하였따...

계속 시간초과야 ㅡ,.ㅡ

 

제출코드

class Queue<T> {
    var enQueue: [T]
    var deQueue: [T] = []
    
    var count: Int {
        return enQueue.count + deQueue.count
    }
    
    var isEmpty: Bool {
        return enQueue.isEmpty && deQueue.isEmpty
    }
    
    init(_ queue: [T]) {
        self.enQueue = queue
    }
    
    func push(_ element: T) {
        enQueue.append(element)
    }
    
    func pop() -> T {
        if deQueue.isEmpty {
            deQueue = enQueue.reversed()
            enQueue.removeAll()
        }
        return deQueue.popLast()!
    }
    
}

let input = Int(readLine()!)!
var arr = [Int](1...input)
var myQueue = Queue<Int>(arr)


for _ in 1 ..< input{
    let _ = myQueue.pop()
    myQueue.push(myQueue.pop())
}
print(myQueue.pop())

 

저작자표시 (새창열림)

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

Swift 백준 1874번) 스택 수열  (2) 2022.09.12
Swift 백준 10816번) 숫자 카드 2 (삽질..)  (2) 2022.08.31
Swift 백준 11650번) 좌표 정렬하기  (0) 2022.08.22
Swift 백준 11050번) 이항계수 1  (0) 2022.08.16
Swift 백준 10866번) 덱  (0) 2022.08.15

수 찾기 성공

 
시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB 154089 45592 30312 29.849%

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다.

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

예제 입력 1 복사

5
4 1 5 2 3
5
1 3 7 9 5

예제 출력 1 복사

1
1
0
0
1

출처

알고리즘 분류

 

코드

import Foundation

//N(1 ≤ N ≤ 100,000)
//M(1 ≤ M ≤ 100,000)

let N = Int(readLine()!)!
var arr_N = readLine()!.split(separator: " ").map{ Int($0)! }

let M = Int(readLine()!)!
var arr_M = readLine()!.split(separator: " ").map{ Int($0)! }

for i in 0..<N{
    let num_m = arr_M[i]
    if arr_N.contains(num_m){
        print(1)
    }else{
        print(0)
    }
}

너무 쉽다고 생각한후 이렇게 코드작성을 하니 당연히 시간 초과가 났다,,,

카테고리에 이진탐색을 발견후 코드를 바꿔줬다.

 

제출코드

import Foundation

//N(1 ≤ N ≤ 100,000)
//M(1 ≤ M ≤ 100,000)

func binarySearch(_ arr: [Int], _ target: Int) -> Int{
    var start = 0
    var end = arr.count - 1

    while start <= end {
        let mid = (start + end) / 2
            if arr_N[mid] == target {
                return 1
            }else if arr_N[mid] > target {
                end = mid - 1
            }else if arr_N[mid] < target {
                start = mid + 1
            }
        }
        return 0
}

let N = Int(readLine()!)!
var arr_N = readLine()!.split(separator: " ").map{ Int($0)! }

let M = Int(readLine()!)!
var arr_M = readLine()!.split(separator: " ").map{ Int($0)! }

arr_N.sort()

for i in 0..<M{
    print(binarySearch(arr_N, arr_M[i]))
}
저작자표시 (새창열림)

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

Swift 백준 10866번) 덱  (0) 2022.08.15
Swift 백준 10854번) 큐  (0) 2022.08.15
Swift 백준 2751번) 수 정렬하기 2  (0) 2022.08.09
Swift 백준 10989번) 수 정렬하기 3  (0) 2022.08.09
Swift 백준 2231번) 분해합  (0) 2022.08.08

+ Recent posts

티스토리툴바