백준 알고리즘 문제 기록/집합과 맵

백준 Swift [1269] 대칭 차집합

Lust3r 2023. 8. 11. 16:57
728x90

난이도

실버 IV

 

문제

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

 

1269번: 대칭 차집합

첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어

www.acmicpc.net

 

내 답안

let nm = readLine()!.split(separator: " ").map { Int($0)! }

var a = Set(readLine()!.split(separator: " ").map { Int($0)! })
var b = Set(readLine()!.split(separator: " ").map { Int($0)! })

var differenceCount = 0

for element in a {
    if !b.contains(element) {
        differenceCount += 1
    }
}

print(differenceCount + (b.count - (a.count - differenceCount)))

- 각각을 배열에 넣고, 다른 수 만큼 계산하는 방식을 사용
  두 배열을 각각 검사할 필요 없이 하나의 배열 값만 비교하면 그 배열의 differenceCount만큼 다른 배열에 있다는 것이므로 그걸 사용하는
  것이 효율적일 것이라 생각했다.

- 하지만 print문에서 filter로 비교한 것에서 1차 시간 초과, differenceCount를 만들고 contains한 것에서 2차 시간 초과가 났고

  이정도면 contains의 O(n)이 문제다 싶어 a와 b의 타입을 Set으로 바꿔 contains를 O(1)로 만들자 통과할 수 있었다.

 

 

 

새로 배운 점

subtracting(_:) | Apple Developer Documentation

 

subtracting(_:) | Apple Developer Documentation

Returns a new set containing the elements of this set that do not occur in the given set.

developer.apple.com

  • 기 제출자 답안을 보는 와중, subtracting 메서드가 눈에 띄었다.
  • 공식문서를 보니 Returns a new set containing the elements of this set that do not occur in the given set 이라고 한다
    • 파라미터로 주어진 다른 set과 비교하여 그 set에 포함되지 않는 요소를 포함한 새로운 set을 반환하는 메서드
    • 즉, 이 문제에서 a.subtracting(b)를 하면 [1]이 반환되는 것이고, 그것의 count를 사용하면 쉽게 해결할 수 있는 것 같다.
저작자표시 비영리 변경금지 (새창열림)