Top Interview Questions
Easy Collection
LEVEL : 🌕 🌕 🌑 🌑 🌑 (하)
Easy Collection의 여섯번째 문제인 Intersection of Two Arrays II를 풀어봤습니다.
이번 문제는 제목과 동일하게 두개의 배열에 있는 원소들의 교집합을 찾는 문제였습니다.
두 Array에 있는 공통적인 원소들을 찾는 것이라서 간단해보일 수 있지만 들어오는 Array에 따라 다양한 조건을 충족시켜줘야 했기 때문에 조금 복잡한 감이 있었습니다.
이번 코드들은 다양한 시도 끝에 답이 나왔기 때문에 답을 보고 싶으신 분들은 4️⃣ 번째 방법부터 보시면 되겠습니다.
1️⃣ 번째 방법
실패한 방식입니다.
처음에 교집합이라는 단어를 보자마자 Set를 써야겠구나. 생각했습니다.
Set에는 intersection이라는 직접 교집합을 찾아주는 함수가 있습니다.
이걸 이용해서 교집합을 찾으면 되겠구나. 라고 생각했는데, 아니었습니다.
예를 들어, nums1 = [1, 2, 2, 1] num2 = [1, 1] 이라고 한다면 답은 [1, 1]이 나와야 합니다.
하지만Set은 자체적으로 중복을 제거해버리기 때문에 답으로 나오는 값은 [1]뿐인거죠.
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var setNums1 = Set<Int>()
for i in nums1 {
setNums1.insert(i)
}
setNums1 = setNums1.intersection(nums2)
return Array(setNums1)
}2️⃣ 번째 방법
또 다른 실패 방식
그럼 중복이 생길 수 있게 해야겠다. 생각했습니다.
일단 두 배열 중 더 짧은 코드로 for문을 돌리면서 긴 배열에 있는 숫자가 contain되어 있으면 result라는 배열에 넣는거죠.
하지만 해당 코드도 문제가 있습니다. 반대로 중복이 생겨버렸어요.
예를 들어, nums1 = [1, 2, 3] nums2 = [1, 1] 라고 했을 때 답으로 [1]이 나와야 합니다.
하지만 답으로 [1, 1]이 나와요.
왜냐면 짧은 배열을 기준으로 하기 때문에 1이 nums1에 있는지 2번 확인하기 때문이죠. 그렇다고 해서 긴 배열로 for문을 돌리면 해결되는 문제도 아닙니다.
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var result: [Int] = []
if nums1.count > nums2.count {
for num in nums2 {
if nums1.contains(num) {
result.append(num)
}
}
} else {
for num in nums1 {
if nums2.contains(num) {
result.append(num)
}
}
}
return result
}3️⃣ 번째 방법
또또 다른 실패 방식
그래서 이번에는 중복을 확인한 숫자는 사라지도록 remove함수를 사용했습니다.
전에 있던 코드에서 remove만 추가했는데, 위에 있는 예시가 해결되었습니다.
하지만, submit를 했더니 또 다른 문제가 생겼습니다.
32번째 case에서 Wrong이 떴더라구요.. 분명 중복을 제거한다고 했는데 제대로 안되는지 문제가 계속 생겼습니다..😂
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var result: [Int] = []
var arr: [Int] = []
if nums1.count > nums2.count {
arr = nums1
for num in nums2 {
if arr.contains(num) {
result.append(num)
arr.remove(at: arr.firstIndex(of: num) ?? 0)
}
}
} else {
arr = nums2
for num in nums1 {
if nums2.contains(num) {
result.append(num)
arr.remove(at: arr.firstIndex(of: num) ?? 0)
}
}
}
return result
}4️⃣ 번째 방법
드디어 성공했습니다.
하지만 위에 실패한 코드들과 약간 다릅니다. 위에 있는 코드에서는 num1, num2의 count별로 case를 나눴다면 해당 코드는 case를 나누지 않고 진행했어요.
case 나눈 거 때문에 위 코드에 문제가 생긴거라면 너무 맘이 아프네요🥲
해당 코드도 위와 동일하게 contains된 부분들을 삭제해줬어요.
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var result: [Int] = []
var arr: [Int] = []
arr = nums1
for num in nums2 {
if arr.contains(num) {
result.append(num)
arr.remove(at: arr.firstIndex(of: num)!)
}
}
return result
}하지만, Runtime이 많이 걸리더라구요. 544ms나 걸렸습니다..
그래서 Runtime를 짧게 만들기 위한 방식을 찾아봤습니다.
5️⃣ 번째 방법
Runtime이 Best인 방식이었습니다.
그리고 Dictionary를 사용한 점이 굉장히 인상깊었던 방식입니다.
코드를 설명하자면,
먼저 Dictionary인 dic를 하나 만들어주고 해당 Dictionary에 key값과 value값을 모두 Int로 받는다고 명시해줍니다.
그리고 먼저 num1에 있는 값들을 하나씩 세줍니다.
dic[num, default: 0] += 1 이 부분이 뭔가 싶을 수도 있는데요.
예를 들자면, num1 = [1, 2, 3, 1, 2]라고 할 때에 저 for문을 돌린다고 하면,
dic안의 값은 [ 1 : 2, 2 : 2, 3 : 1 ]이 됩니다.
for문에서 들어온 num값이 key값으로 들어가는데 그 전에 들어왔던 적이 없으면 default: 0이 아니라면 전 value에서 +1된 값이 value로 들어옵니다.
완성된 Dictionary를 기준으로해서 nums2에 있는 값들과 비교해줍니다. 안에 nums2에 있는 숫자가 있으면 result에 넣어주고 value값을 -1 해줍니다.
func intersect(_ nums1: [Int], _ nums2: [Int]) -> [Int] {
var dic: [Int: Int] = [:]
for num in nums1 {
dic[num, default: 0] += 1
}
var result = [Int]()
for num in nums2 {
if let freq = dic[num], freq > 0 {
result.append(num)
dic[num] = freq - 1
}
}
return result
}Dictionary를 이런식으로 쓸 수 있다는게 참신했습니다.
당연히 num들을 직접 비교하는 방식을 생각했는데, num가 몇개 있는지 센 후에 진행하는 방식은 처음이었습니다.
아직까지 Swift에서 제공해주는 자료구조들을 다 알진 못해서 문제를 풀 때마다 새로운 자료구조를 배워가는 기분입니다.
Swift 알고리즘 얼른 정복할 겁니다.
