Top Interview Questions
Easy Collection
LEVEL : 🌕 🌕 🌑 🌑 🌑 (하)
Easy Collection의 세번째 문제인 Rotate Array를 풀어봤습니다.
제목 그대로 배열을 Rotate하는 로직 짜기가 문제였습니다.
전 문제들처럼 쉽게 풀 거라고 예상했지만 시간 초과가 났고, 시간복잡도가 O(n)의 효율을 낼 수 있는 코드를 생각하다보니 자연스레 코드 자체가 좀 복잡해졌습니다.
코드를 보여드리면서 설명하겠습니다.
1️⃣ 번째 방법
첫번째 방법은 시간 초과가 난 로직입니다.
그렇기 때문에 바로 정답을 보고 싶으시다면 2번째 방법부터 보시는 걸 추천드립니다.
시간 초과가 난 이유를 저도 정확히 알 것 같습니다.
문제가 생긴 이유
일단 머릿속으로 정리했을 때, 맨 뒤에 있는 element가 앞으로 오고 앞에 있는 것들이 차례대로 뒷줄로 밀려나야한다고 생각이 들어서 이중 for문을 사용했습니다.
해당 문제는 전제로 1<= element 갯수 <= 10^5 만큼의 배열크기가 들어올 수 있다고 했기 때문에 숫자가 커짐에 따라 시간 초과 문제가 발생한 것 같습니다.
func rotate(_ nums: inout [Int], _ k: Int) {
if nums.count > 1 {
for _ in 0..<k {
let num = nums[nums.count-1]
for j in (0...nums.count-2).reversed() {
nums[j+1] = nums[j]
}
nums[0] = num
}
}
}
2️⃣ 번째 방법
이중 for문이 안된다면 O(n)의 효율이 나도록 단일 for문만 돌려야 된다는 생각이 들었습니다.
하지만 단일 for문을 사용해서 어떻게 이중 for문과 같은 효율을 내지 싶더라구요.
그래서 공간 복잡도를 늘리는 대신, 배열을 하나 더 만들기로 했습니다.
해당 배열에 nums에 있는 숫자들을 k부터 차곡차곡 넣다가 다시 0~k-1까지 넣는 방식으로 구현했습니다.
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
라고 한다면
sub = [#, #, #, 1, 2, 3, 4] 를 먼저 넣고
sub = [5, 6, 7, 1, 2, 3, 4] 를 다음에 넣어주는거죠.
func rotate(_ nums: inout [Int], _ k: Int) {
var sub = [Int](repeating: 0, count: nums.count)
for i in 0..<nums.count {
sub[(i + k) % nums.count] = nums[i]
}
for i in 0..<nums.count {
nums[i] = sub[i]
}
}일단, sub라는 배열은 배열의 크기를 초기화해줘야 합니다.
알고리즘하면서 [Int](repeatint:0, count: nums.count) 이렇게 처음 써봅니다..
그냥 var sub: [Int] = [ ] 이렇게 사용하면 out of range 오류가 뜨더라구요. 빈 배열이기 때문에 그렇겠죠.
그리고 안에서 (i + k) % nums.count를 사용해서 위의 방식을 구현해줬습니다.
해당 식으로 계산하게 되면 k = 3일 때는 3부터 sub라는 배열에 숫자가 차게되고 이후에 (i + k)값이 nums.count값 이상으로 가게되어 0부터 다시 숫자가 시작되기 때문에 해당 방식을 구현할 수 있게 됩니다.
2번째 방식은 Runtime이 아주 빨랐습니다.👍
3️⃣ 번째 방법
3번째 방법은 대표 답안으로 작성되어 있던 걸 Swift로 구현한 방식입니다.
대표 답안 자체가 Leetcode에서는 Java, 아니면 Python으로 되어 있기 때문에 방식이 다소 Java 코드 같을 수 있습니다.
하지만 효율은 2번째 방식보다 5ms정도 더 좋았습니다.
func rotate(_ nums: inout [Int], _ k: Int) {
let l = k % nums.count
var count = 0
for start in 0..<nums.count where count < nums.count {
var current = start
var prev = nums[start]
repeat {
let next = (current + l) % nums.count
let temp = nums[next]
nums[next] = prev
prev = temp
current = next
count += 1
} while (start != current)
}
}해당 방식은 코드로 보기에도 이해하기가 복잡합니다.
간단하게 설명하자면
이런 방식입니다.
저는 2번째 방식이 훨씬 짜기 쉽다고 생각이 들어서 3번째 방식은 참고해서 짜는걸로 만족했습니다.
요건 뭐지?
저는 알고리즘으로 처음 배우는 문법이 많았습니다. 너무 뷰 짜는데만 Swift를 쓴 거 같다는 생각이 들더라구요..
그 문법 중 하나가 repeat-while이었습니다.
repeat-while은 do-while과 동일한 기능을 하는 친구입니다.
do-while과 사용 방식은 동일하기 때문에 설명은 더 안하겠습니다.!
4️⃣ 번째 방법
제가 생각하기에 가장 간단하고 편한 방식인 거 같습니다.
func rotate(_ nums: inout [Int], _ k: Int) {
if k < 1 || nums.isEmpty {
return
}
let k = k % nums.count
nums = Array(nums[nums.count - k..<nums.count] + nums[0..<nums.count-k])
}Runtime도 가장 좋고 코드도 쉽습니다.
Swift의 Array는 Subscript를 사용해서 배열의 값을 범위만큼 가져올 수 있습니다.
이 점을 이용해서 코드를 짰습니다.
앞부분엔 k+1 인덱스부터 끝까지 가져온 elements를 넣고 뒷부분엔 앞부터 k까지의 elements들을 넣어서 앞에서 귀찮게 for문돌렸던 걸 쉽게 해결했습니다.
