Swift ) 프로그래머스(Lv3) - 보석 쇼핑 (TwoPointer & Hash)

programmers.co.kr/learn/courses/30/lessons/67258

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

안녕하세요 후르륵짭짭 입니다.

지금 까지 모든 프로그래머스 Lv2를 다 끝내고 이제,, Lv3를 문제를 풀게 됐습니다.

결론 부터 말하면,,, Lv2는 어떻게 생각하면 풀 수 있지만,,, Lv3는 아직 많이 부족한 것 같습니다.

두 문제 밖에 안 풀어봤지만,,, Lv1에서 Lv2로 올라간 만큼 Lv2에서 Lv3로 올라간 것 같습니다.

그럼 문제에 본격적인 해설을 하도록 하겠습니다.

 

 

** 저의 해설 **

func solution(_ gems:[String]) -> [Int] {
    
    var dict : [String : Int] = [:]
    var answer : [(start : Int , end : Int, len : Int)] = []
    
    let allCount = Set(gems).count
    
    var start = 0
    var end = -1
    
    var cnt = 0
    
    while start < gems.count || end < gems.count {
        
//        print(start , end)
        
        if cnt == allCount {
            
            //스택에 저장
            answer.append((start: start, end: end, len: end - start))
            
            if let exist = dict[gems[start]]{
                
                if exist - 1 == 0 {
                    
                    dict.removeValue(forKey: gems[start])
                    cnt -= 1
                }
                else{
                    
                    dict[gems[start]] = exist - 1
                }
                
            }
            
            start += 1
            
        }
        else{
            
            end += 1
            
            if end < gems.count{
            
            if let exist = dict[gems[end]] {
                dict[gems[end]] = exist + 1
            }
            else{
                dict[gems[end]] = 1
                cnt += 1
            }
                
            }
            
        }
        
        if end >= gems.count && cnt < allCount{
            break
        }
        
    }
    
    answer = answer.sorted(by: { (element1, element2) -> Bool in
        
        if element1.len == element2.len{
            return element1.start < element2.start
        }
        
        return element1.len < element2.len
    })
        
    return [answer.first!.start + 1 , answer.first!.end + 1]
}

이 문제를 저 혼자만의 힘으로 풀지 못했습니다.

정확성은 통과 할 수 있겠지만,,, 효율성을 어떻게 통과하면 좋을지 몰랐고,,, TwoPointer라는 것은 알았지만,,,

어떻게 활용해야할지 잘 몰랐습니다.

 https://tech.kakao.com/2020/07/01/2020-internship-test/

2020 카카오 인턴십 for Tech developers 문제해설

여기의 설명을 보고 그대로 구현 했습니다.

로직은 포인터 두개를 가지고 O(n) 시간 만에 해결 하는 겁니다.

예를들어

S D D E D S 가 있다고 했을 때, 

1. Set을 사용해서 독립적인 요소의 갯수를 구합니다. 그러면 SDE 가 나옵니다. 총 세개 입니다.

2. 이제 start 와 end 포인터 두개를 만들어 줍니다. start는 시작 점 end는 끝점을 말합니다.

3. 반복문을 통해 독립적인 요소를 세어주는 cnt를 만들어 줍니다.

4. cnt가 독립적인 요소 개수인 세개가 아닐 때 까지 end를 증가시켜줍니다.

 - 그런데 여기서 hash를 사용해서 존재 여부를 판단해줍니다. 존재한다면 한개 씩 증가시켜줍니다.

- 없다면 dictionary에 넣어주고 cnt 갯수도 증가 시켜줍니다.

- end는 반드시 입력된 string 보다 작아야하니, 조건문을 달아 줍니다.

else{
            
            end += 1
            
            if end < gems.count{
            
            if let exist = dict[gems[end]] {
                dict[gems[end]] = exist + 1
            }
            else{
                dict[gems[end]] = 1
                cnt += 1
            }
                
            }
            
        }

5. 이제 cnt가 독립된 갯수랑 같아지면 시작점 ,끝점 , 그리고 길이를 stack에 저장해줍니다.

 - 그리고 dictionary에서 그 이름을 가져오고 빼줍니다. 그 때 값이 0이라면 딕셔너리에서 완전히 삭제 시켜줍니다.

- 그리고 한칸 앞으로 이동 해줍니다.

 if cnt == allCount {
            
            //스택에 저장
            answer.append((start: start, end: end, len: end - start))
            
            if let exist = dict[gems[start]]{
                
                if exist - 1 == 0 {
                    
                    dict.removeValue(forKey: gems[start])
                    cnt -= 1
                }
                else{
                    
                    dict[gems[start]] = exist - 1
                }
                
            }
            
            start += 1
            
        }

여기 까지의 내용을 예시로 들자면

S D D E D S 에서 cnt가 3개가 처음 되는 지점이 S D D E 입니다. 그러면 이제 0 부터 3 을 저장해줍니다.

이제 꽉 찼으니 start를 한칸 앞으로 가게 해주면서 S를 지워줍니다.

D D E 가 되는데, cnt가 2가 됐기 때문에 end를 늘려줍니다.

D D E D S 가 됩니다. 또 위의 과정을 반복해주면 start가 계속 앞으로 이동 하게 되고

E D S 까지 저장해줍니다.

이제 E를 빼주면 D S 가 되고 end를 증가 시켜주는데, 더 이상 저장 할 것도 없고 cnt 갯수가 동일 하지 않기 때문에 반복문을 종류해줍니다.

if end >= gems.count && cnt < allCount{
            break
        }

 

마지막에 정렬 해서 첫번 째 요소를 반환해줍니다.

    answer = answer.sorted(by: { (element1, element2) -> Bool in
        
        if element1.len == element2.len{
            return element1.start < element2.start
        }
        
        return element1.len < element2.len
    })
        
    return [answer.first!.start + 1 , answer.first!.end + 1]

 

처음으로 TwoPointer랑 Hash를 사용해서 처음으로 문제를 풀어 봤습니다. 이런 유형은 처음 였기 때문에 생각하기 쉽지 않았습니다.

내일이면 카카오 시험인데 3문제를 목표로 제발 ㅠㅠ