Programmers Lv3) [2020 카카오 인턴십] 보석쇼핑

출처: programmers.co.kr/learn/courses/30/lessons/67258

분류: Lv3, 카카오 인턴십, 투 포인터

---

접근방식

투 포인터 방식으로 해결했습니다. 

먼저 전체 보석 종류의 개수를 구해놓고 포인터를 움직이면서 모든 보석이 들어있는 경우를 체크해주는 방식입니다.

저는 처음에 조금 비효율적으로 접근했는데요,

보석의 개수를 체크해주면서 현재 시작 포인터의 보석이 여러 개라면 현재 보석을 더 들고 있을 필요가 없으니 포인터를 옮겨주는 방식을 사용했습니다. 

전체 과정을 좀 더 설명드리면,

저는 시작 포인터가 끝에 도달할 때까지 반복문을 돌려주면서

먼저 보석이 모두 들어있는지 체크해서 최선이라면 결과를 바꿔주고

끝 포인터를 움직이면서 보석에 담아줍니다.

그리고 현재 시작 포인터의 보석이 여러 개 있는지 확인해줍니다.

while start < gems.count {
  if currentGemSet.count == gemCount {
    if result[1] - result[0] > end - start {
    	result = [start+1, end+1]
    }
  }

  if end < gems.count-1 {
    end += 1
    gemDictionary[gems[end], default: 0] += 1
    currentGemSet.insert(gems[end])
  } else {
    gemDictionary[gems[start]]! -= 1
    if gemDictionary[gems[start]] == 0 {
    currentGemSet.remove(gems[start])
  }
  	start += 1
  }



  while start < gems.count, let count = gemDictionary[gems[start]], count > 1 {
    gemDictionary[gems[start]]! -= 1
    if gemDictionary[gems[start]]! == 0 {
    	currentGemSet.remove(gems[start])
    }
    start += 1
  }
}

 

하지만 다른 분들의 풀이를 보니까 굳이 이렇게 개수를 일일이 세줄 필요가 없더라구요!

개수를 체크해줄 필요 없이 그냥 각 보석의 인덱스를 계속 갱신해주면

보석이 모두 들어있을 때, 보석들의 인덱스 중 가장 작은 값과 큰 값이 범위가 됩니다 :)

 

해결방법

import Foundation

func solution(_ gems:[String]) -> [Int] {
    let gemCount = Set<String>(gems).count
    var gemDictionary = [String: Int]()
    
    var start = 0
    var end = 0
    
    var currentGemSet = Set<String>()
    currentGemSet.insert(gems[0])
    gemDictionary[gems[0]] = 1
    var result = [1, 100000]
    
    while start < gems.count {
        if currentGemSet.count == gemCount {
            if result[1] - result[0] > end - start {
                result = [start+1, end+1]
            }
        }
        
        if end < gems.count-1 {
            end += 1
            gemDictionary[gems[end], default: 0] += 1
            currentGemSet.insert(gems[end])
        } else {
            gemDictionary[gems[start]]! -= 1
            if gemDictionary[gems[start]] == 0 {
                currentGemSet.remove(gems[start])
            }
            start += 1
        }
        
        
        
        while start < gems.count, let count = gemDictionary[gems[start]], count > 1 {
            gemDictionary[gems[start]]! -= 1
            if gemDictionary[gems[start]]! == 0 {
                currentGemSet.remove(gems[start])
            }
            start += 1
        }
    }
    
    return result
}

 

배운점

세상에 똑똑한 사람들이 참 많다.