1764번: 듣보잡

문제 풀이 아이디어

# 써야할 자료구조 = set
    : 두 명단을 받아서 겹치는 것을 구하는 문제입니다.
    : 교집합 연산을 활용하면 됩니다.

# 문제 풀이 아이디어
    : 듣도 못한 집합 하나, 보도 못한 집합 하나를 선언합니다.
    : 입력을 받고 교집합을 구합니다.
    : 정렬한 후 정렬해서 출력한다.

# 의사코드
    1. 첫줄 인풋을 받고 빈 집합 2개 선언합니다.
    2. n과 m만큼 반복문을 돌면서 두개의 집합에 넣습니다.
    3. 두 집합의 교집합을 구합니다.
    4. 리스트로 바꿔서 정렬하고 출력합니다.

# 시간복잡도
    : 반복문 n과 m번 두개 니까 O(2n) = O(n)
        : 집합에 삽입은 O(1)
    : 교집합은 O(len(s1) + len(s2))
        : 정리하면 결국 O(n)
    : 정렬은 O(nlogn)
    : 최종적으로 O(n) + O(n) + O(nlogn) = O(nlogn)
    : n이 500,000이니까 충분합니다.

Set을 활용한 풀이

// 갯수 입력 받기
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = nums[0], M = nums[1]

// 집합 선언
var s1 = Set<String>()
var s2 = Set<String>()

// 이름 입력 받아서 set에 저장
for _ in 0..<N {
    s1.insert(readLine()!)
}

for _ in 0..<M {
    s2.insert(readLine()!)
}

// 교집합 구하기
var result = s1.intersection(s2)

// 정렬해서 출력
print(result.count)
for name in result.sorted() {
    print(name)
}

참고) swift의 집합 연산

var s1 = Set<String>()
var s2 = Set<String>()

// 합집합
var union = s1.union(s2) //👉 새로운 변수에 할당
s1.formUnion(s2) //👉 s1에 합집합 재할당

// 교집합
var intersection = s1.intersection(s2) //👉 새로운 변수에 할당
s1.formIntersection(s2) //👉 s1에 교집합 재할당

// 차집합
var subtraction = s1.subtracting(s2)  //👉 새로운 변수에 할당
s1.subtract(s2) //👉 s1에 차집합 재할당

// 대칭차 (합집합 - 교집합)
var symmetricDifference = s1.symmetricDifference(s2) //👉 새로운 변수에 할당
s1.formSymmetricDifference(s2) //👉 s1에 대칭차 재할당

Dictionary (Hash table)을 활용한 풀이

삽입과 탐색이 O(1)인 Dictionary를 활용한 풀이입니다. 집합을 이용한 풀이와 시간 복잡도가 O(nlogn)으로 동일합니다.

// 갯수 입력 받기
let nums = readLine()!.split(separator: " ").map { Int(String($0))! }
let N = nums[0], M = nums[1]

// Dictionary 활용
var dict = [String : Int]()

// 듣지 못한 사람 저장 -> O(1)
for _ in 0..<N {
    dict[readLine()!] = 0
}

// 보지 못한 사람 저장
    // 듣지 못한 사람에 있는지 확인 -> O(1)
    // 있다면 저장
for _ in 0..<M {
    let name = readLine()!
    if dict[name] != nil {
        dict[name] = 1
    }
}

// 결과 추출
    // value 확인 -> O(1)
    // array에 append -> O(1)
var result = [String]()
for key in dict.keys {
    if dict[key] == 1 {
        result.append(key)
    }
}

// 결과 출력
print(result.count)
result.sorted().forEach { name in //👉 배열 정렬 -> O(nlogn)
    print(name)
}