14171 swift - Cities and States

[Swift] (자료구조) 해쉬 / Hash

 

처음에 시간 제한이 2초라서 널널하게 보고 2중 for문을 돌렸다가 호되게 시간초과 맞고,
두번째는 저장부터 해시로 저장하자 했는데 중복 값때문에 호되게 틀렸습니다.

 

14171번: Cities and States

맞은 코드

import Foundation

var n = Int(readLine()!)!
var m = [String: Int]()
var arr = [String]()
var cnt = 0

for _ in 0..<n {
	let parts = readLine()!.split(separator: " ").map(String.init)
	let city = parts[0]
	let statesCode = parts[1]
	let key = String(city.prefix(2) + statesCode)
	arr.append(key)
	m[key, default: 0] += 1
}

for key in arr {
	let rStr = String(key.suffix(2) + key.prefix(2))
	if key == rStr { continue }
	if let count = m[rStr] {
		cnt += count
	}
}

print(cnt / 2)

 

 

 

시간초과 코드

let N = Int(readLine()!)!
var dic = [String: String]()
var count = 0

for _ in 0..<N {
	let d = readLine()!.split{$0 == " "}.map{String($0)}
	dic[d[0]] = d[1]
}

for n in dic {
	for m in dic {
		let find = String(m.key.suffix(2))
		find == n.value ? count += 1 : nil
	}
}

print(count)

중복처리 안한 코드

let N = Int(readLine()!)!
var dic = [String: String]()
var count = 0

for _ in 0..<N {
	let d = readLine()!.split{$0 == " "}.map{String($0)}
	dic[d[0]] = d[1]
}

for n in dic {
	if let _ = dic[n.value] { count += 1 }
}

print(count)