String 타입 문제의 두 번째 시간.
1. Valid Anagram
Anagram이라는 말을 처음 들어봤을 것이다. 아래의 예를 봐보자.
"하녕안요세"
이 단어를 보면 생각나는 말이 있는가??
배치를 좀 다르게 하면 "안녕하세요"가 된다.
Anagram은 해리포터에서도 등장했었는데,
TOM MARVOLO RIDDLE를 풀면
"I AM LORD VOLDEMORT" 로 바뀌는 장면이 있었다.
즉, A로 B를 만들 수 있는지를 체크하면 되는 문제이다.
이를 위해서는 원소의 갯수가 동일한지 파악해보면 된다.
바로 코드로 가자.
class Solution {
func isAnagram(_ s: String, _ t: String) -> Bool {
// key & value로 묶기 위해 dictionary 사용
var dic = [Character:Int]()
// 원 배열에서 등장한 만큼 1씩 추가
for c in s {
dic[c, default:0] += 1
}
// 뒤죽박죽된 배열에서 등장한 만큼 1씩 빼기
for c in t {
dic[c, default:0] -= 1
}
// 모든 Value가 0이어야 Anagram이다.
for (k,v) in dic {
if v != 0 {
return false
}
}
return true
}
}
[ 프로세스 ]
1. 빈 dictionary 객체를 만든다.
2. 원배열(s)의 key & value를 추가한다. (+1)
3. 원배열(s)의 key를 기준으로 뒤죽박죽된 배열(t) key와 매칭될 경우 value를 1 낮춘다 (-1)
4. dictionary의 value가 모두 0이라면 anagram이라는 것이고, 아닐 경우 anagram이 아니기에 false를 반환한다.
처음에는 위 처럼 dictionary를 생성하지 않고 아래처럼 했었는데, 메모리/런타임이 비효율적이어서 앞으로도 그냥
위에 방법으로 생성하고자 한다.
// 기존 방법
var strS = Dictionary(s.map {($0,1)}, uniquingKeysWith: +)
var strT = Dictionary(t.map {($0,1)}, uniquingKeysWith: +)2. Valid Palindrome
Palindrome이란 문장을 뒤집어도 원래 문장과 같을 경우를 말한다.
한국어로 치면 "수박이 박수"를 거꾸로 해도 똑같아지는 경우와 같을 때, Palindrome이라고 한다.
이를 위해 특수문자를 제외한 문자열(소문자)만 남겨야 하고, 문자열을 뒤집어야한다.
바로 코드를 봐보자.
처음에는 아래와 같은 방식으로 풀이했었다.
class Solution {
// 기존 풀이
func isPalindrome2(_ s: String) -> Bool {
// 잡아낼 문자열들 세팅
var stdChr = "abcdefghijklmnopqrstuvwxyz1234567890"
var res = ""
// 소문자로 변환
for i in s.lowercased() {
// 기준에 속할 경우 append
if stdChr.contains(i) {
res.append(i)
}
}
// 기존 문자열을 뒤집는다
let resRev = String(res.reversed())
return res == resRev
}
}
[ 프로세스 ]
1. 먼저 추출해야할 문자열의 값을 세팅해둔다.
2. 기존 String이 기준에 부합할 경우 res에 append한다.
3. 기존 문자열을 뒤집는다.
4. 비교한다.
이렇게 했을 때, 통과는 되나 런타임/메모리가 비효율적이라는 결과를 얻었다.
그래서 배열로 접근하는 방법, 기준을 만들지 않고 기존 메서드를 사용해보는 방식으로 방향을 틀었다.
class Solution {
func isPalindrome(_ s: String) -> Bool {
// 빈 배열 생성
var res = [Character]()
// 소문자로 만들고
for chr in s.lowercased() {
// 문자 or 숫자일 경우,
if chr.isLetter || chr.isNumber {
// append 한다.
res.append(chr)
}
}
// index를 설정해주고
var left = 0
var right = res.count - 1
// 만나기 전 까지
while left < right {
// 다를 경우 Palindrome이 아님
if res[left] != res[right] { return false}
// index 진행
left += 1
right -= 1
}
return true
}
}
[ 프로세스 ]
1. 정제된 값을 담을 빈 배열을 생성한다.
2. 소문자로 변경한 s의 원소들을 돌며
2-1. 문자 or 숫자인지 파악 후
2-2. res에 append 한다.
3. 양 끝 index를 설정해주고
4. index들이 만나기 전까지 while문을 돌며
4-1-1. left, right 인덱싱 값이 다를 경우 palindrome이 아니기에 false 반환함
4-2. 인덱스 값 +- 진행하여 다음 케이스 확인
5. 이상 없을 경우 palindrome이기에 true 반환