Top Interview Questions
Easy Collection
LEVEL : 🌕 🌕 🌑 🌑 🌑 (하)
Easy Collection String의 세번째 문제인 First Unique Character in a String를 풀어봤습니다.
이번 문제는 String 속에서 한 번만 나타나는 Character를 찾고 해당 Character의 index를 return하는 문제였습니다.
저는 문제를 보자마자 Stack를 사용하면 되겠다! 했는데, 중복이라는 게 2개만 있는 게 아닌데 2개라고 안일하게 생각해버린거였습니다..
3개도 나올 수 있고 4,5.. 무한정으로 등장할 수 있기 때문에 Stack은 절대 알맞지 않더라구요.
대신 다른 방법들을 찾아봤습니다.
1️⃣ 번째 방법
첫 번째 방법은 Dictionary를 사용했습니다.
두 개의 Dictionary를 만들었는데요, 첫 번째는 Character가 나오는 Count를 세는 용, 두 번째는 Character의 index를 저장하는 용으로 만들었어요.
두 개로 나눈 이유는 Dictionary에는 순서가 없어서, 하나씩 찬찬히 넣어줘도 뒤죽박죽이 되어 버립니다...😂
일단 첫 번째 for문을 통해서 s에 포함되어 있는 character가 lists에 key값으로 포함되어 있는지 보고,
없으면
해당 key값을 넣고 value로 0를 넣어줍니다. 그리고 indexs에는 해당 값이 들어온 적이 없다면 index값을 value로 넣어줍니다.
있으면
해당 char를 가지고 있는 value값을 +1 해줍니다.
그리고 두 번째 for문에서는 indexs도 마찬가지로 뒤죽박죽이기 때문에 value를 중심으로 sort를 먼저해주고 그에 맞춰서 key값과 index값을 꺼냅니다.
꺼낸 key값이 list에서 0를 출력한다면 그 index를 return해줍시다.
두 번째 for문에서 return되지 못했다면 모든 character가 중복이라는 뜻이기 때문에 -1를 return하면 됩니다.
func firstUniqChar(_ s: String) -> Int {
var lists: [Character: Int] = [:]
var indexs: [Character: Int] = [:]
for (index, char) in s.enumerated() {
if lists.keys.contains(char) {
if let num = lists[char] {
lists.updateValue(num+1, forKey: char)
}
} else {
lists[char] = 0
if !indexs.keys.contains(char) {
indexs[char] = index
}
}
}
for (key, index) in indexs.sorted(by: { $0.1 < $1.1 }) {
if lists[key] == 0 {
return index
}
}
return -1
}
Runtime은 보시는대로 276ms가 걸렸습니다. 전체에서 중간정도의 Runtime이 걸렸습니다.
시간을 줄이고 싶어서 다른 분들이 짠 코드를 봤는데, 너무 신선한 방식들이라서 가져와 봤습니다.
2️⃣ 번째 방법
이 방식이 현재 Runtime이 가장 빠르다라고 되어 있어서 봤는데, 너무 신선했습니다.
방식이 엄청 어려운 것은 아닌데, 이렇게도 풀 수 있었는데 싶었던 방식이었습니다.
제가 처음에 c언어를 배울 때 많이 사용하던 방식이었는데요.
바로 유니코드를 사용하는 방식입니다.
일단 Array를 만들고 26칸을 생성해줍니다. 소문자 알파벳의 갯수라고 생각하시면 됩니다.
그리고 각 칸에는 0으로 초기화를 해줘요.
우리는 'a'의 유니코드를 기본으로 해서 그에 맞춰서 각 character에 index를 부여할 겁니다.
예를 들어서 'c'가 들어온다면, 'c'는 유니코드로 99에 해당하기 때문에 'c' - 'a'를 하게 되면 2가 나오게 됩니다. counter[2]는 c가 들어가는 칸이 되고 우리가 생각했던 index에 맞춰 들어가는 걸 알 수 있죠?
각 character가 index에 맞춰서 들어가면 해당 index에 들어있는 숫자가 +1씩 증가하게 됩니다.
즉, 0이면 아무것도 안들어옴. 1이면 1개, 2면 2개가 들어온거죠.
그리고 두 번째 for문에서 counter의 값이 1이면 해당 index(i)를 return 합니다.
첫 번째와는 다르게 배열을 사용했기 때문에 이미 들어오는대로 정렬이 잘 되어 있어서 따로 sorted를 안해도 되고 Array를 이미 26개의 자리에 맞춰서 만들어둬서 훨씬 편합니다.
extension UnicodeScalar {
var intValue: Int {
return Int(value)
}
}
func firstUniqChar(_ s: String) -> Int {
var counter = Array(repeating: 0, count: 26)
let a_unicode = UnicodeScalar("a").intValue
for c in s.unicodeScalars {
counter[c.intValue - a_unicode] += 1
}
var i = 0
for c in s.unicodeScalars {
if counter[c.intValue - a_unicode] == 1 {
return i
}
i += 1
}
return -1
}
Runtime이 쏙 내려간 걸 알 수 있습니다.
3️⃣ 번째 방법
가장 Runtime이 빨랐어요.! 분명 이중 for문을 썼는데 제일 빨라서 놀랐습니다.
이번에는 Array와 Set를 사용했습니다.
이번 문제는 chars에 있는 문자를 하나씩 빼내서 자신의 index 뒤에 있는 모든 문자들과 하나씩 대조해보면서 푸는 문제였습니다.
만약에 같은 문자가 뒤에 있다면 그 문자는 skipChars라는 Set에다가 넣어두고 다음에 그 문자 차례가 왔을 때 where조건에 걸려서 그 문자는 다시 for문을 돌지 못하게 했습니다.
그리고 뒤에 자신과 같은 문자가 없다면 isUnique라는 Boolean타입을 true로 만들어서 해당 index를 return하게 해줬습니다.
func firstUniqChar(_ s: String) -> Int {
let chars: [Character] = [Character](s)
var skipChars: Set<Character> = []
for i in 0 ..< chars.count where !skipChars.contains(chars[i]) {
var isUnique: Bool = true
for j in i + 1 ..< chars.count {
guard isUnique else { break }
if chars[i] == chars[j] {
isUnique = false
skipChars.insert(chars[i])
break
}
}
if isUnique { return i }
}
return -1
}
보시다시피 시간이 굉장히 빨랐습니다. 이중 for문인데도 불구하고 Runtime이 가장 빠르게 나왔어요!!
아마도 contains되는 애들을 바로바로 제외시키기도 했고, 또 for문을 돌려서 return하는 게 아니라 지금 상태에서 Unique하다면 바로 그 index를 return시키는 방식으로 해서 그런지 빠른게 아닌가 싶습니다.
