[Swift 백준]1620번_Dictionary VS Array

백준 문제를 풀다 생긴 일이다. 

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

1620번: 나는야 포켓몬 마스터 이다솜

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까지 빨라진다!