백준 : 2776번 - 암기왕 swift

pengsang·2023년 7월 26일

swift 백준 알고리즘

문제풀이

목록 보기

3/11

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

문제예시

1. 입력

2. 출력

실패 코드 1 -> 시간 초과(완전탐색)

let input = Int(readLine()!)!
var result = [Int]()

for _ in 0..<input {
    let numberOfNBook1 = Int(readLine()!)!
    let arrOfBook1 = readLine()!.split(separator: " ").map{Int($0)!}
    let numberOfNBook2 = Int(readLine()!)!
    let arrOfBook2 = readLine()!.split(separator: " ").map{Int($0)!}
    
    for j in arrOfBook2{
        if arrOfBook1.contains(j) {
            print(1)
        }else {
            print(0)
        }
    }
}
print(result)

실패코드 2 -> 시간초과(이진탐색)

이진탐색을 이용하였으나 100만이 넘는 정수배열을 정렬하는 과정에서 시간복잡도가 급격히 증가하여 시간초과가 난다고 추정

let input = Int(readLine()!)!

for _ in 0..<input {
    var hash = [Int : [Int]]()

    let _ = Int(readLine()!)!
    let arrOfBook1 = readLine()!.split(separator: " ").map{Int($0)!}.sorted()
    let _ = Int(readLine()!)!
    let arrOfBook2 = readLine()!.split(separator: " ").map{Int($0)!}
    
    for i in arrOfBook2 {
        if binaraySearch(arrOfBook1, i) != -1 {
            print(1)
        }else {
            print(0)
        }
    }
}

func binaraySearch(_ arr: [Int], _ value: Int ) -> Int{
    var left = 0
    var right = arr.count - 1
    
    while left <= right {
        let mid = left + (right - left)/2
        
        if value == arr[mid] {
            return mid
        }else if value > arr[mid] {
            left = mid + 1
        }else {
            right = mid - 1
        }
    }
    return -1
}

이진탐색으로도 문제가 해결되지 않는 현상이 나타나 구글링을 해봄
-> 결과로 입출력 속도에 의해 시간초과가 나타나기도 한다고 함
-> 빠른 입출력 코드를 이용해 문제를 해결하기로 결정

풀이과정

우선 라이노님의 빠른 입출력 클래스를 이용하기로 함
이진탐색을 이용하려면 탐색 대상 배열이 정렬된 상태로 되어있어야 하므로 시간복잡도가 늘어남. 따라서 해쉬를 이용하기로 함

해쉬를 이용해 해당 값이 들어있는지 Bool 자료형을 이용해 확인
수첩 2에 들어갈 정수를 입력해 해쉬테이블에 해당 값이 포함되어 있는지 확인
-> 들어있으면 1을 출력
-> 없으면 0을 출력

코드

해당 코드는 라이노님의 빠른 입출력 클래스를 이용한 풀이다
빠른 입출력 코드의 경우 xcode에서는 정상적으로 실행되지 않는 이슈가 있음을 기억해야 한다

import Foundation

final class FileIO {
    private let buffer: Data
    private var index: Int = 0
    
    init(fileHandle: FileHandle = FileHandle.standardInput) {
        self.buffer = try! fileHandle.readToEnd()! // 인덱스 범위 넘어가는 것 방지
    }
    
    @inline(__always) private func read() -> UInt8 {
        defer {
            index += 1
        }
        guard index < buffer.count else { return 0 }
        
        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 str = ""
            var now = read()

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

            while now != 10
                    && now != 32 && now != 0 {
                str += String(bytes: [now], encoding: .ascii)!
                now = read()
            }

            return str
        }
  }


let fIO = FileIO()
let testCases = fIO.readInt()

for _ in 0..<testCases {
    var hash = [Int: Bool]()
    let n = fIO.readInt()
    for _ in 0..<n {
        let number = fIO.readInt()
        hash[number] = true
    }
    let m = fIO.readInt()
    for _ in 0..<m {
        let a = fIO.readInt()
        if hash[a] == true {
            print(1)
        } else {
            print(0)
        }
    }
}

다른 유저의 풀이과정

Set를 이용한 탐색을 이용한 풀이과정이다
Set는 해쉬를 이용한 자료구조로 키(key)만 저장한 결과로 중복을 허용하지 않는다. 또한 배열과 다르게 특정 대상을 contains를 이용해 탐색하는데 시간복잡도가 O(1)이므로 매우 빠르다
반면에 배열은 탐색 contains를 이용해 탐색할 경우 최악의 경우 시간복잡도가 O(N)이다

let n = Int(readLine()!)!

for _ in 0..<n {
    var answer = [String]()
    
    let _ = readLine()!
    let arr = Set(readLine()!.split(separator: " ").map { Int($0)! })
    
    let _ = readLine()!
    readLine()!.split(separator: " ").forEach { char in
        arr.contains(Int(char)!) ? answer.append("1") : answer.append("0")
    }
    
    print(answer.joined(separator: "\n"))
}