Top Interview Questions
Easy Collection
LEVEL : 🌕 🌑 🌑 🌑 🌑 (최하)
Easy Collection의 첫번째 문제인 Remove Duplicates from Sorted Array를 풀어봤습니다.
영어로 문제가 써져있다보니 문제를 해석하는 것부터가 어렵더라구요.
하지만 문제 제목에서 유추할 수 있듯이 Sorted된 Array에 있는 중복된 숫자를 제거하는 문제였습니다.
처음 풀었을 때도 고작 코드 3-4줄로 Solved를 했고 나중에 Runtime를 줄이기 위해서 다른 방식을 찾았을 때도 10줄이 안넘었던 거 같네요.
그럼 제가 문제를 해결해갔던 방향을 한 번 설명드리겠습니다.
1️⃣ 번째 방법
Duplicate라는 단어를 보자마자 생각났던게 Set이었습니다.
아시다시피 Set에 넣은 element들은 모두 중복이 제거된 상태로 저장이 됩니다.
그렇기 때문에 처음에 들어온 배열을 Set를 사용해서 중복을 제거해주고, 그 후에 .sorted()를 하는 방식을 선택했습니다.
func removeDuplicates(_ nums: inout [Int]) -> Int {
let numset = Set(nums)
nums = numset.sorted()
return nums.count
}이렇게 코드를 짰더니, 결과는 Success
하지만, Runtime이 길더라구요.
그래서 시간을 줄이기 위한 여정이 시작되었습니다.
2️⃣ 번째 방법
혹시나 Set를 쓴 게 많은 시간을 소요한 건 아닐까 싶어서 이번엔 Set없이 for문으로 돌렸습니다.
func removeDuplicates(_ nums: inout [Int]) -> Int {
var numset: [Int] = []
for n in nums {
if !numset.contains(n) {
numset += [n]
}
}
nums = numset
return nums.count
}
하지만, 전보다 더 긴 시간이 소요됐어요... 340ms..🥲
3️⃣ 번째 방법
Set도 for문도 아니면 뭘까. 엄청 생각을 하다가 뭔가 제가 신경쓰지 않고 있던 게 있다는 걸 깨달았습니다.
그건 바로 "numset"
그냥 nums에서 처리하면 됐던 걸 numset까지 만들면서 nums와 numset으로 값을 왔다갔다 옮기고 있더라구요..
그래서 nums에서만 처리할 수 있도록 코드를 짰습니다.
func removeDuplicates(_ nums: inout [Int]) -> Int {
guard nums.count > 1 else { return nums.count }
var cnt = 0
for index in 1..<nums.count {
if nums[index] == nums[index-1]{
cnt += 1
} else {
nums[index-cnt]=nums[index]
}
}
return nums.count - cnt
}
결과는 56ms ! Set를 사용했을 때랑 30ms정도밖에 차이는 안나지만 쉬운 문제였기 때문에 시간에 집착을 좀 해봤습니다.
🙃 inout
이번 문제를 풀면서 처음 본 inout이라는 문법.
함수의 파라미터를 함수 내부에서 변경하고 함수가 종료된 후에도 변경한 값이 지속되도록 하려면 변수의 주소값을 넘겨 직접 접근할 수 있도록 도와주는 inout 키워드 사용
그렇다고 하네요. 파라미터를 함수 내부에서도 변경할 수 있도록 써주는 키워드라고 합니다.
전에 배웠던 C, C++에 있던 포인터가 생각나는 키워드입니다.
위에 써있는 것처럼 주소값을 넘겨줘야 하기 때문에 C, C++과 동일하게 &를 사용해서 인수를 명시해줘야 합니다.
func start() {
var ber = [1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 7]
let num: Int = removeDuplicates4(&ber)
}이렇게 말이죠.
알고리즘 공부하면서 배워가는 것도 많은 것 같습니다.
# inout reference
