백준 문제를 풀다 생긴 일이다.
https://www.acmicpc.net/problem/1620
1620번: 나는야 포켓몬 마스터 이다솜
첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면
www.acmicpc.net
1. Array만 사용 (시간 초과)
맨 처음에는 Array만을 사용했다. Index를 사용해서 번호를 구분할 생각이었다.
func 나는야_포켓몬마스터_이다솜() {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
var pokedex = [String]()
var answer = ""
for _ in 1...input[0] {
let pokemon = readLine()!
pokedex.append(pokemon)
}
for _ in 1...input[1] {
let question = readLine()!
if let number = Int(question) {
answer += "\(pokedex[number - 1])\n"
} else {
let pokemonIndex = pokedex.firstIndex(of: question)
answer += "\(pokemonIndex! + 1)\n"
}
}
print(answer)
}
나는야_포켓몬마스터_이다솜()그런데 이렇게 했더니 시간 초과가 났다!
firstIndex를 확인하면서 O(n)이라 오래걸리는 것 같았다.
2. Dictionary 2개 사용 (맞았습니다, 256ms)
Dictionary나 Set 등 HashValue로 값을 찾는 경우는 Array보다 조금 더 빠르다. 굳이 전부 돌아볼 필요가 없기 때문이다.
func 나는야_포켓몬마스터_이다솜() {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
var numberPokedex = [Int: String]()
var namePokedex = [String: Int]()
var answer = ""
for i in 1...input[0] {
let pokemon = readLine()!
numberPokedex[i] = pokemon
namePokedex[pokemon] = i
}
for _ in 1...input[1] {
let question = readLine()!
if let number = Int(question) {
answer += "\(String(describing: numberPokedex[number]!))\n"
} else {
answer += "\(String(describing: namePokedex[question]!))\n"
}
}
print(answer)
}
나는야_포켓몬마스터_이다솜()그러나 value값으로 key 값을 찾는 것은 hashValue를 이용한 것이 아니기에 반대되는 것까지 Dictionary를 두 개 만들어 구분하였다.
하지만 더 나은 방법이 없을까 고민했다.
3. Dictionary와 Array의 사용 (맞았습니다, 204ms)
이름을 key, 번호를 value로 하는 경우는 어쩔 수 없지만, 반대의 경우는 array의 subscript로 접근할 수 있다.
func 나는야_포켓몬마스터_이다솜() {
let input = readLine()!.split(separator: " ").compactMap { Int($0) }
var numberPokedex = [String]()
var namePokedex = [String: Int]()
var answer = ""
for i in 1...input[0] {
let pokemon = readLine()!
numberPokedex.append(pokemon)
namePokedex[pokemon] = i
}
for _ in 1...input[1] {
let question = readLine()!
if let number = Int(question) {
answer += "\(numberPokedex[number - 1])\n"
} else {
answer += "\(namePokedex[question]!)\n"
}
}
print(answer)
}
나는야_포켓몬마스터_이다솜()그랬더니 시간이 훨씬 줄어들었다. 찾아서 사용하는 것보다는 subscript를 통한 접근이 훨씬 빠른 것 같다.
++ func 없이 실행하면 188ms까지 빨라진다!