Top Interview Questions
Easy Collection
LEVEL : 🌕 🌕 🌑 🌑 🌑 (하)
Easy Collection의 다섯번째 문제인 Single Number를 풀어봤습니다.
이번 문제는 중복없이 혼자만 존재하는 숫자를 찾는 문제였습니다.
앞에 문제들이 중복 제거나 중복 확인을 하는게 대부분이여서 다른 문제들의 방식을 사용할 수도 있었어요. 하지만 되게 특이한 방식도 있더라구요, 소개해드리고 싶어서 가져왔습니다.
먼저 기본적인 방법부터 코드를 보여드리면서 설명하겠습니다.
1️⃣ 번째 방법
전에 중복이 있는지 찾아내는 로직을 조금 수정했습니다.
nums에 있는 숫자가 1개라면 바로 그 숫자를 return하고,
그 이상이라면 먼저 sorted를 한 후에 양 옆의 숫자들이 같은 수인지 확인하는 방식으로 로직을 짰습니다.
해당 index의 수와 index+1의 수가 같다면 index+2해주는 식으로 해서 이미 확인한 수를 다시 확인하지 않도록 했습니다. 그리고 양 옆에 숫자가 같지 않다면 그 수가 바로 혼자 존재하는 수이기 때문에 해당 숫자를 return하도록 했습니다.
하지만 nums 맨 끝에 있는 수가 혼자 존재하는 수이고, nums에 들어있는 수가 홀수라면 while조건에 따라서 맨 끝에 있는 수를 확인하지 못하게 됩니다. 하지만 그 수가 혼자 존재한다는 건 명백하기 때문에 while문을 원만하게 통과했다면 return를 num에 있는 마지막 숫자로 했습니다.
func singleNumber(_ nums: [Int]) -> Int {
guard nums.count > 1 else { return nums[0] }
let num = nums.sorted()
var index = 0
while index < nums.count-1 {
if num[index] == num[index+1]{
index += 2
} else {
return num[index]
}
}
return num[nums.count-1]
}해당 방식이 runtime은 느렸지만 memory측면에서는 좋았습니다.
2️⃣ 번째 방법
해당 방식은 memory측면에서는 좋지 않지만 중복을 문제에 자주 등장하는 Set를 이용한 문제였습니다.
일단 Set를 하나 만들어두고 nums에 있는 숫자를 Set이 가지고 있다면 remove하고 가지고 있지 않다면 insert하는 방식으로 로직을 구현했습니다.
전 코드보다 이해하기도 쉽고 runtime도 전보다 빠르게 나왔습니다.
contains된 것만 지우기 때문에 결국 혼자있는 숫자는 나갈 수가 없는 형태인거죠. 그 점을 이용해서 for문을 돌리고 배열에 있는 첫번째 원소를 return 했습니다.
func singleNumber(_ nums: [Int]) -> Int {
var tempNums = Set<Int>()
for value in nums {
if tempNums.contains(value) {
tempNums.remove(value)
} else {
tempNums.insert(value)
}
}
return tempNums.first!
}3️⃣ 번째 방법
runtime이 가장 좋은 방법이며, 생각지도 못한 방법이었습니다.
일단 코드부터 보여드리겠습니다.
func singleNumber(_ nums: [Int]) -> Int {
var result = 0
for num in nums {
result ^= num
}
return result
}코드가 매우 짧고, 간결합니다.
하지만 저는 처음부터 이해하진 못했습니다. ^= 이 친구가 무슨 뜻인지 도통 몰랐거든요.
^= 는 뭘까?
XOR(^)를 아시나요?
우리가 아는 OR(||)은 비교하는 두 개의 값 중 하나만 True여도 True를 return합니다.
XOR은 OR과는 다르게 두 개의 값이 다른 값을 가지고 있어야 True를 return합니다.
한마디로 1(true) ^ 0(false) = 1(true) 인거죠.
^=은 result = result ^ num를 뜻합니다.
두 값의 XOR값이 result로 들어올 겁니다.
^=를 써서 어떻게 문제를 푼다는거죠?
저도 처음에 ^=와 중복이 무슨 상관이라고 저 방식을 사용한다는 거지. 우연히 해보니깐 된건가?
이렇게 생각했습니다.
하지만 XOR의 의미를 이해한다면 충분히 저 방식으로 풀어낼 수 있더라구요.
예시를 들어보겠습니다.
nums = [1, 2, 3, 2, 3] 이라고 하겠습니다.
처음에 1이 들어오면 0 ^ 1 => 0000 ^ 0001 = 0001(1) 이 됩니다.
2가 들어오면 1 ^ 2 => 0001 ^ 0010 = 0011(3) 이 됩니다.
3이 들어오면 3 ^ 3 => 0011 ^ 0011 = 0000(0) 이 됩니다.
2가 들어오면 0 ^ 2 => 0000 ^ 0010 = 0010(2) 이 됩니다.
3이 들어오면 2 ^ 3 => 0010 ^ 0011 = 0001(1) 이 됩니다.
결국 정답인 1이 나옵니다.
XOR은 같은 자리에 중복으로 나오는 값을 0으로 만들고 서로 다른 값을 1로 만듭니다.
그렇기 때문에 두 개의 숫자가 중복으로 나오면 0010(2) ^ 0010(2) = 0000(0) 이렇게 0이 될 수 밖에 없는거죠.
결국 중복으로 나타나 자신의 숫자를 지울 값이 없는 숫자만이 살아남게 됩니다.
그 원리를 사용해서 문제를 푼 거구요.
XOR, NOR, XAND 등등 이런걸로 한 번도 뭘 해보겠다는 생각이 없었는데, 이렇게 간단하게 풀기에 좋다니.. 너무 신기하더라구요. 정말 공부해야할 게 많고 가야할 길이 멀다는 걸 또 느낍니다.
