[백준/Swift] 1620 - 나는야 포켓몬 마스터 이다솜

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

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

 

처음 풀이 :

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let N = input[0]
let M = input[1]
var dic:[Int:String] = [:]
var answer:[String] = []

for i in 1...N {
  dic[i] = readLine()!
}

for _ in 0..<M {
  let input = readLine()!
  if input.first!.isLetter { //문자 -> 인덱스
    let index = dic.firstIndex(where: { $0.value == input })!
    answer.append(String(dic[index].key))
  }
  else{
    answer.append(dic[Int(input)!]!)
  }
}

print(answer.joined(separator:"\n"))

- 이 코드는 자꾸 시간초과가 났다. 딕셔너리를 사용해서 숫자가 들어온다면 그 key에 해당하는 value를 출력하고, 문자가 들어온다면 그 문자를 value를 가지고 있는 인덱스를 찾아 해당 딕셔너리의 인덱스에 접근해서 key를 출력해주었다.

- 왜 시간초과가 났나 확인해보니 "N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데" 라고 되어있어서 수의 범위가 크고, 추측해보건데 dic.firstIndex 이부분이 탐색을 위해서 걸리는 시간복잡도가 O(n)이니까 반복문안에 있으니까 O(n^2) 이 되어버려서 시간초과가 난건 아닐까 추측이 된다.

- 따라서 다른 분들의 풀이를 찾아봤고, key-value가 int-String, String-int인 딕셔너리를 각각 만들어서 입력이 들어올때마다 각각 순서를 바꾸어 저장한다음에 넣어두면 바로 접근이 가능하기때문에 시간복잡도가 O(1)으로 확 줄어든다.

- 이후에 유사한 문제를 마주쳤을 때 "딕셔너리 2개를 만들어버리자" 라는 교훈을 얻었다.

 

최종 풀이 : 

let input = readLine()!.split(separator:" ").map { Int(String($0))! }
let N = input[0]
let M = input[1]
var dic1:[Int:String] = [:]
var dic2:[String:Int] = [:]
var answer:[String] = []

for i in 1...N {
  let input = readLine()!
  dic1[i] = input
  dic2[input] = i
}

for _ in 0..<M {
  let input = readLine()!
  if input.first!.isLetter { //문자 -> 인덱스
    answer.append(String(dic2[input]!)!)
  }
  else{
    answer.append(dic1[Int(input)!]!)
  }
}

print(answer.joined(separator:"\n"))