[알고리즘 연습] 보석 쇼핑 (프로그래머스 lv3, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/67258?language=swift

코딩테스트 연습 - 보석 쇼핑

풀이

func solution(_ gems:[String]) -> [Int] {
​​​​
​​​​var start = 0
​​​​var end = 0
​​​​let totalCount = Set(gems).count
​​​​var gemBox = [String:Int]()
​​​​var answer = [1, gems.count]
​​​​
​​​​while end < gems.count {   
​​​​​​​​
​​​​​​​​gemBox[gems[end], default: 0] += 1 
​​​​​​​​
​​​​​​​​while start <= end && gemBox[gems[start]]! > 1 {
​​​​​​​​​​​​gemBox[gems[start]]! -= 1
​​​​​​​​​​​​start += 1
​​​​​​​​}         
​​​​​​​​
​​​​​​​​let nowCount = gemBox.count
​​​​​​​​
​​​​​​​​if totalCount == nowCount &&
​​​​​​​​answer[1] - answer[0] > end - start {
​​​​​​​​​​​​answer = [start+1, end+1]
​​​​​​​​} 
​​​​​​​​
​​​​​​​​end += 1
​​​​}
​​​​
​​​​return answer
}

• 투 포인터 알고리즘을 활용한 문제
• Set(gems).count을 통해 전체 보석개수를 파악하고 이와 같을 경우 값을 비교하여 answer에 기록함
• 현재까지의 보석 개수를 기록하는 dictionary를 만들고 여기에 매번 end좌표의 보석을 넣어줌
• 해당 end좌표에서는 보석들의 중복이 없도록 start좌표를 최대한 늘려줌 (dictionary의 값이 1보다 크면 start를 늘리고 dictionary 내부값을 하나 줄여줌)
• 이러다가 현재 dictionary 지정값이 전체 보석개수와 같다면 값을 확인하여 대입해줌