[백준(BOJ)] 1764 듣보잡 - 스위프트(Swift)

[Silver IV] 듣보잡 - 1764

문제 링크

성능 요약

메모리: 76048 KB, 시간: 80 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 정렬, 문자열

문제 설명

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

 

풀이

처음엔 나타나는 듣도 못한 사람을 구한 뒤, 보도 못한 사람의 값을 받으면서 만약 듣도 못한 사람에 포함되면 배열에 추가해주는 방식으로 풀었습니다. 

여기서 주의할 점은 듣도 못한 사람은 Set을 통해 구현해주어야 하는데, 만약 배열로 구하게 된다면 시간초과가 나타나기 때문입니다.

배열에서 값을 탐색하는 것보다 Set에서 값을 탐색하는 것이 시간적으로 빠르기 때문입니다.

 

다음은 코드입니다.

let nm = readLine()!.split(separator: " ").map { Int($0)! }
let (n, m) = (nm[0], nm[1])
var (noHear, ans) = (Set<String>(), [String]())

for _ in 0..<n {
    let input = readLine()!
    noHear.insert(input)
}

for _ in 0..<m {
    let input = readLine()!

    if noHear.contains(input) {
        ans.append(input)
    }
}

ans.sort()

print(ans.count)
print(ans.joined(separator: "\n"))