알고리즘/백준

[백준/Swift] 10816번: 숫자 카드 2

녕이 2023. 1. 26. 21:13
728x90

 

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

 

10816번: 숫자 카드 2

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

www.acmicpc.net

 

처음에는 이분탐색으로 했는데 시간초과 나서 딕셔너리를 사용해서 해당 카드의 개수를 세고 출력해 주는 방식으로 했다.

 

 

[시간 초과 코드]

import Foundation

let n = Int(readLine()!)!
var sg = readLine()!.split(separator: " ").map{ Int(String($0))! }.sorted()
let m = Int(readLine()!)!
var card = readLine()!.split(separator: " ").map{ Int(String($0))! }
var answer = [Int]()

for i in 0..<m {
    let target = card[i]
    guard sg.contains(target) else {
        answer.append(0)
        continue
    }
    let first = sg.firstIndex(of: target)!
    let last = sg.lastIndex(of: target)!
    answer.append(last - first + 1)
}
print(answer.map{ String($0) }.joined(separator: " "))

 

[정답 코드]

import Foundation

let n = Int(readLine()!)!
var sgDict = [String: Int]()
var sg = readLine()!.split(separator: " ").map{ String($0) }
for i in sg {
    sgDict[i] = (sgDict[i] ?? 0) + 1
}
let m = Int(readLine()!)!
var card = readLine()!.split(separator: " ").map{ String($0) }
var answer = [String]()

card.forEach {
    if sgDict[$0] == nil {
        answer.append("0")
    }else {
        answer.append(String(sgDict[$0]!))
    }
}
print(answer.joined(separator: " "))

 

 

 

728x90